MULPAL - Multiplicative Palindrome

no tags 

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

hide comments
MarioYC: 2012-02-11 13:33:16

disjoint contiguous palindromic subsequences = disjoint palindromic substrings? (looking each number as a character)

Last edit: 2012-12-24 01:17:59
Buda IM (retired): 2011-10-15 21:35:11

Yes, my O ( N ) got TLE, some IO optimization took care of it.

Last edit: 2011-10-15 21:38:26
Prabakaran: 2011-01-26 07:44:32

@Shaka Shadows:In ur post length(11 12 12 11)*length(10),in Y part 10 is not a palindrome.then hw can u consider it?
i think the sol is len(11)*len(11)=4

Kinan Sarmini: 2010-12-17 10:04:15

If anyone is getting WA a lot, then you either forget n = 1 case or long long

Siarhei Kulik: 2010-12-16 19:39:28

Time limit is a little strict. Even O(N) solution may not fit in the time.

.::Manish Kumar::.: 2010-12-12 18:13:40

What was your Time-complexity?

Shaka Shadows: 2010-12-12 02:43:17

Yes :). Besides, X and Y don't need to be one exactly after the other. Read the text carefully.

.::Manish Kumar::.: 2010-12-11 19:16:17

So, ultimately it has nothing to do with numbers, numbers can be considered as a single element.

Last edit: 2010-12-11 19:17:22
Shaka Shadows: 2010-12-11 18:57:22

No, the answer is 4 because length(11 12 12 11) * length(10) = 4 * 1 = 4. The problem asks for finding 2 disjoint and palindromic contiguous sequences, X and Y, such that length(X) * length(Y) is maximum.

.::Manish Kumar::.: 2010-12-11 18:53:09

Is the answer to 3rd sample 4 because:
length(11)*length(11) = 2*2 = 4 ?


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