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 ≤ 106).
Second line will contain N integers representing a sequnce from the text of the task (0 ≤ Ai ≤ 2*109).

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