Given a sequence of N integers. Find two disjoint contiguous palindromic subsequences. Lets call them X and Y. Your task is to find X and Y such that product of their lengths is maximal possible.

Input

First line will contain one integer N (1 ≤ N ≤ 10⁶).

Second line will contain N integers representing a sequence from the text of the task (0 ≤ A_i ≤ 2*10⁹).

Output

First and only line of output should contain only one integer, the maximum possible product from the text of problem.

Example

Input:
2
1 1

Output:
1

Input:
4
1 1 2 2

Output:
4

Input:
6
10 11 12 12 11 10

Output:
4

Input:
6
0 1 0 1 0 1

Output:
9