Longest Palindromic Subsequence

Given an integer array A, your task is to find the maximum length k such that there exists a subsequence C of A which is a palindrome. In other words, determine the length of the longest palindromic subsequence of A. Note that a subsequence is obtained from A by deleting some elements (possibly none) without changing the order of the remaining elements.

The value of k represents the maximum length of C, i.e., the length of the longest palindromic subsequence.

inputFormat

The input consists of two lines:

• The first line contains a single integer n, representing the number of elements in the array A.
• The second line contains n space-separated integers, which are the elements of the array A.

outputFormat

Output a single integer, the maximum length k of a palindromic subsequence that can be formed from the array A.

sample

5
1 2 3 2 1

5