Рекорди навпаки#13116
Дано масив із цілих чисел.
Назвемо позицію рекордною, якщо a_i строго більше за всі елементи, що стоять перед ним. Першу позицію завжди вважаємо рекордною.
Ви можете виконати не більш як одну операцію: вибрати ціле число (1\le k\le n) та розвернути перші елементів масиву.
Наприклад, якщо a=[4,2,5,1,3] та k=3, після операції отримаємо масив [5,2,4,1,3].
Знайдіть максимальну можливу кількість рекордних позицій після виконання не більш як однієї операції.
Перший рядок містить одне ціле число (1\le n\le2\cdot10^5) — довжину масиву.
Другий рядок містить цілих чисел a_1,a_2,\ldots,a_n (1\le a_i\le10^9).
Виведіть одне ціле число — максимальну можливу кількість рекордних позицій.
Приклад 1
Приклад 2
Приклад 3
У першому прикладі можна розвернути перші два елементи й отримати масив [1,2,5,3,4]. Рекордними будуть позиції .
У другому прикладі можна розвернути весь масив та отримати [1,2,3,4]. Усі чотири позиції будуть рекордними.
У третьому прикладі можна розвернути перші чотири елементи й отримати [2,1,3,3,3]. Рекордними будуть позиції та . Отримати більше двох рекордних позицій неможливо.
Підзадача ( балів): n\le100.
Підзадача ( балів): n\le2000.
Підзадача ( балів): без додаткових обмежень.