SPOJ.com - Problem MULPAL

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

Submit solution!

hide comments

< Previous 1 2 Next >

	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) = 22 = 4 ?

Submit solution!

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