MULPAL - Multiplicative Palindrome

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 sequence 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

Added by:Zvonimir Medic
Date:2010-11-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem

hide comments
2010-12-11 18:45:02 Zvonimir Medic
contiguous
2010-12-11 18:45:02 Shaka Shadows
Does the problem ask for subsequences or contiguous sequences? I mean, in test:
6
10 11 12 12 11 10

10 10 may be considered?

Last edit: 2010-12-11 18:09:32
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.