В турнире по программированию участвуют \(n\) коров. Корова \(i\) имеет рейтинг Cowdeforces, равный \(a_i\) (все значения разные), и изначально находится на позиции \(i\). Турнир состоит из \(n-1\) матча, проводимых следующим образом:
- Первый матч проводится между коровой на позиции \(1\) и коровой на позиции \(2\).
- В дальнейшем матч \(i\) проводится между коровой на позиции \(i+1\) и победителем матча \(i-1\).
- В каждом матче корова с более высоким рейтингом Cowdeforces побеждает и переходит к следующему матчу.
Вы являетесь владельцем коровы \(k\). Для вас не важна победа в турнире, скорее, вы хотите, чтобы ваша корова выиграла как можно больше матчей. Будучи знакомым организаторов турнира, вы можете попросить их поменять место вашей коровы с другой коровой только один раз, или же вы можете ничего не делать.
Найдите максимальное количество побед, которое может одержать ваша корова.
Выходные данные
Для каждого набора входных данных выведите одно целое число: максимальное количество побед коровы \(k\), которого можно достичь, если сделать оптимальный обмен (или ничего не делать).
Примечание
При первом наборе входных данных оптимально ничего не делать. Пусть \(a'\) — это рейтинги на Cowdeforces коров в изначальном порядке (при этом рейтинг вашей коровы выделен жирным шрифтом), тогда
- Изначально, \(a' = [\mathbf{12}, 10, 14, 11, 8, 3]\).
- Ваша корова играет против коровы с рейтингом Cowdeforces \(10\) и выигрывает. \(a' = [\mathbf{12}, 14, 11, 8, 3]\).
- Ваша корова играет против коровы с рейтингом Cowdeforces \(14\) и проигрывает.
В общей сложности ваша корова выигрывает в
\(1\) матче.
Во втором наборе входных данных оптимально поменять вашу корову с коровой на позиции \(3\). Тогда пусть \(a'\) — это рейтинги на Cowdeforces коров в порядке после обмена позициями.
- Изначально, \(a' = [7, 2, \mathbf{12}, 10, 727, 13]\).
- Корова с рейтингом Cowdeforces \(7\) играет против коровы с рейтингом Cowdeforces \(2\) и выигрывает. \(a' = [7, \mathbf{12}, 10, 727, 13]\).
- Корова с рейтингом Cowdeforces \(7\) играет против вашей коровы, и ваша корова побеждает. \(a' = [\mathbf{12}, 10, 727, 13]\).
- Ваша корова играет против коровы с рейтингом Cowdeforces \(10\) и выигрывает. \(a' = [\mathbf{12}, 727, 13]\).
- Ваша корова играет против коровы с рейтингом Cowdeforces \(727\) и проигрывает.
В общей сложности ваша корова выиграет
\(2\) матча.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 1
12 10 14 11 8 3
6 5
7 2 727 10 12 13
2 2
1000000000 1
|
1
2
0
|