Гарний краєвид#11749

Гарний краєвид

1 секунда

128 мегабайтів

Дуже складна

Париж переповнений туристами під час Олімпійських ігор! Ви хочете втекти з міста і вирушити в похід лінійним маршрутом. На цьому маршруті кожен кілометр, включаючи початок та кінець, позначений кілометровим каменем, на якому вказана висота каменю. Ухил між двома сусідніми каменями постійний і жодні два камені не мають однакової висоти.

Плануючи повернутися сюди з друзями, Ви намагаєтеся знайти точку походу, з якої був найгарніший краєвид. Краса точки краєвиду визначається як відстань (виміряна в кілометрах) між Вашою поточною позицією та попередньою позицією на маршруті, на якій висота була такою самою. Якщо такої попередньої позиції не існує, це означає, що Ви бачите місто та його смоґ і краса цього краєвиду дорівнює нулю.

Ви записали висоти всіх кілометрових каменів. Якою є максимальна краса на вашому маршруті?

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5) — кількість кілометрових каменів на маршруті. Другий рядок містить $n$ цілих чисел $h_{1}, h_{2}, \dots, h_{n}$ h_1, h_2, \ldots, h_n; кожне ціле число $h_{k}$ h_k ( $0 \leq h_{k} \leq 1 0^{6}$ 0 \le h_k \le 10^6, $h_{k}$ h_k попарно різні) — це висота (виміряна в метрах) $k$ -го кілометрового каменя на маршруті.

Вихідні дані

Виведіть одне число $s$ : максимальний показник краси на вашому маршруті. Це число записується у вигляді цілого числа, або у вигляді нескоротного дробу $n / d$ , для якого $d \geq 2$ d \ge 2; нагадаємо, що дріб $n / d$ є нескоротним, якщо найбільший спільний дільник чисел $n$ і $d$ дорівнює $1$ .

Приклади

Приклад 1

Приклад 2