На практических занятиях в университете Кселлосу однажды довелось измерять интенсивность эффекта, медленно приближающегося к состоянию равновесия. Хороший способ измерить интенсивность в такой системе — это выбрать достаточно большое количество последовательных частных значений, кажущихся почти одинаковыми, и взять их среднее значение. Конечно, при обычных размерах данных в этом нет ничего сложного, но почему бы не сделать из этого задачу для соревнований по программированию?
Вам дана последовательность из n значений a1, a2, ..., an. Между последовательными значениями не бывает больших скачков — для любого 1 ≤ i < n гарантируется, что |ai + 1 - ai| ≤ 1.
Диапазон значений [l, r] называется почти постоянным, если разница между наибольшим и наименьшим значением в этом диапазоне не превышает 1. Формально, пусть M максимальное, а m — минимальное значение ai при l ≤ i ≤ r, тогда диапазон [l, r] почти постоянен, если M - m ≤ 1.
Найдите максимальную длину почти постоянного диапазона.
В первой строке входных данных записано целое число n (2 ≤ n ≤ 100 000) — длина последовательности ai.
Во второй строке записано n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 100 000).
Выведите единственное число — максимальную длину почти постоянного диапазона данной последовательности.
5
1 2 3 3 2
4
11
5 4 5 5 6 7 8 8 8 7 6
5
В первом примере максимальным по длине почти постоянным диапазоном является [2, 5]; его длина равна 4.
Во втором примере имеется три почти постоянных диапазонов длины 4: [1, 4], [6, 9] и [7, 10]. Почти постоянный диапазон максимальной длины 5 только один: [6, 10].
| Codeforces Round 333 (Div. 2) |
|---|
| Закончено |
