P. Сколько проходов у пузырька

Пузырьковая сортировка делает проходы по массиву, пока хоть один обмен происходит. Проход, на котором обменов не случилось, тоже считается — именно он и сообщает, что массив уже упорядочен.

Сколько проходов понадобится? Для уже отсортированного массива ответ равен единице, а для массива из одного элемента — нулю: проходить нечего.

В первой строке $n$ от $1$ до $1000$. Во второй — $n$ целых чисел, каждое по модулю не больше $1000$.

Одно число.