Longest Palindromic Subsequence

You are given a string s consisting of lowercase English letters and its length n. Your task is to compute the length of the longest palindromic subsequence in s.

A subsequence is a sequence that can be derived from the string by deleting some or no elements without changing the order of the remaining elements. A palindrome is a string that reads the same backwards as forwards.

This problem can be formulated as finding the maximum length L such that there exists a subsequence s' of s with length L and s' is a palindrome.

The dynamic programming approach uses the recurrence relation:

[ dp[i][j] = \begin{cases} 1 & \text{if } i=j,\ 2 & \text{if } s_i = s_j \text{ and } j=i+1,\ dp[i+1][j-1] + 2 & \text{if } s_i = s_j,\ \max(dp[i+1][j],\ dp[i][j-1]) & \text{if } s_i \neq s_j. \end{cases} ]

Your solution should read input from stdin and write the answer to stdout.

inputFormat

The input is given from stdin as follows:

1. The first line contains an integer n representing the length of the string.
2. The second line contains the string s, which consists of lowercase English letters.

outputFormat

Output a single integer to stdout, the length of the longest palindromic subsequence of s.

## sample

1
a

1