Массив называется «горным» (Mountainous), если он сначала строго возрастает, а затем строго убывает. Заметим, что «горные» массивы должны иметь длину не менее трех.

Подмассив определяется как массив, который можно получить путем удаления некоторого префикса и суффикса (возможно, пустых) из исходного массива.

Массив или подмассив называется палиндромом, если он читается одинаково в обоих направлениях.

Дан массив целых чисел. Вычислите длину самого длинного подмассива, который является одновременно «горным» и палиндромом.

Входные данные

Первая строка входных данных содержит целое число $n$ ($1 \le n \le 10^6$), количество целых чисел в массиве. Каждая из следующих $n$ строк содержит одно целое число $x$ ($1 \le x \le 10^9$). Эти значения образуют массив. Они даны в порядке следования.

Выходные данные

Выведите единственное целое число — длину самого длинного «горного» палиндромного подмассива, или $-1$, если такого подмассива не существует.

Примеры

Пример 1

8
2
1
2
3
2
1
7
8

Выходные данные 1

5

Пример 2

5
2
5
8
7
2

Выходные данные 2

-1