给定一个字符数组，编写一个程序来找出该数组中最长的回文子序列的长度。回文是指正读和反读都相同的字符串。

第一行输入数组的长度n（1 < n <= 1000）；
第二行输入n个字符，组成的序列。

最长回文子序列的长度。

7
r a c e c a r

7

样例2输入

8
z h a n g n h z

样例2输出

3