ICPC North America Championship 2021

Start

2021-08-14 07:00 AKDT

ICPC North America Championship 2021

End

2021-08-14 10:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -69 days 0:01:30

Time elapsed

3:30:00

Time remaining

0:00:00

Problem F
Mountainous Palindromic Subarray

An array is Mountainous if it is strictly increasing, then strictly decreasing. Note that Mountainous arrays must therefore be of length three or greater.

A Subarray is defined as an array that can be attained by deleting some prefix and suffix (possibly empty) from the original array.

An array or subarray is a Palindrome if it is the same sequence forwards and backwards.

Given an array of integers, compute the length of the longest Subarray that is both Mountainous and a Palindrome.

Input

The first line of input contains an integer $n$ ($1 \le n \le 10^6$), which is the number of integers in the array.

Each of the next $n$ lines contains a single integer $x$ ($1 \le x \le 10^9$). These values form the array. They are given in order.

Output

Output a single integer, which is the length of the longest Mountainous Palindromic Subarray, or $-1$ of no such array exists.

Sample Input 1 Sample Output 1
8
2
1
2
3
2
1
7
8
5
Sample Input 2 Sample Output 2
5
2
5
8
7
2
-1