ある配列が「山型（Mountainous）」であるとは、厳密に増加した後に厳密に減少することを指す。山型配列は、定義上長さが3以上でなければならないことに注意せよ。

「部分配列（Subarray）」とは、元の配列から接頭辞と接尾辞（空でもよい）を削除することで得られる配列として定義される。

配列または部分配列が「回文（Palindrome）」であるとは、前から読んでも後ろから読んでも同じ並びであることを指す。

整数の配列が与えられたとき、山型かつ回文であるような最長の部分配列の長さを求めよ。

入力

入力の1行目には、配列に含まれる整数の個数を表す整数 $n$ ($1 \le n \le 10^6$) が与えられる。 続く $n$ 行の各行には、整数 $x$ ($1 \le x \le 10^9$) が1つずつ与えられる。これらの値は順に配列を構成する。

出力

山型かつ回文であるような最長の部分配列の長さを出力せよ。そのような部分配列が存在しない場合は $-1$ を出力せよ。

入出力例

入力 1

8
2
1
2
3
2
1
7
8

出力 1

5

入力 2

5
2
5
8
7
2

出力 2

-1