Задача №115143. Самокат
В городе Новый Нижгород открылась новая служба доставки еды с оригинальным названием «Камосат». Курьеры этой службы передвигаются на самокатах и стремятся максимально эффективно доставлять заказы клиентам.
Для того чтобы упростить задачу планирования маршрутов, был разработан алгоритм, основанный на топографии города. Город расположен вдоль реки, поэтому его можно представить одномерным массивом, где каждый элемент массива — это высота местности в соответствующей точке. Расстояние между двумя соседними точками считается равным \(1\).
Каждый курьер начинает свой маршрут в некоторой точке города. Он может двигаться только вправо (по увеличению номеров элементов массива) и посещать только те точки, где высота меньше , чем в точке старта . Курьер стремится проехать как можно дальше, учитывая данное условие. Курьер, встретив местность не ниже , чем точка старта, не может продолжить путь.
Помогите курьерам определить длину максимального маршрута, по которому они могут проехать, выбрав произвольную точку старта.
Первая строка содержит одно целое число \(n\) (\(2 \leq n \leq 300\,000\)) — количество точек в городе.
Вторая строка содержит \(n\) целых чисел \(h_1, h_2, \ldots, h_n\) (\(-10^9 \leq h_i \leq 10^9\)) — высоты точек города.
Выведите одно целое число — максимальное расстояние, которое может преодолеть курьер.
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при монотонном массиве высот (т.е. когда для всех \(1 \le i < n\) выполняется \(h_i \leq h_{i+1}\) или для всех \(1 \le i < n\) выполняется \(h_i \geq h_{i+1}\)), наберут не менее \(14\) баллов.
Решения, корректно работающие при \(n \leq 2000\), наберут не менее \(28\) баллов.
В первом примере курьер может стартовать в третьей точке с высотой \(6\) и проехать по высотам \(6\rightarrow2\rightarrow1\).
Во втором примере курьер не может никуда проехать, потому что можно посещать только те точки, где высота меньше, чем в точке старта.
В третьем примере курьер может проехать по высотам \(5\rightarrow2\rightarrow3\rightarrow4\).
7 5 4 6 2 1 9 3
2
2 1 1
0
5 4 5 2 3 4
3