Longest Palindromic Subsequence

Given a string $s$, find the length of the longest subsequence of $s$ that is a palindrome.

A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters. A palindrome reads the same forwards and backwards.

Input

The first line contains an integer $n$, the length of the string.

The second line contains the string $s$.

Output

Output one integer: the length of the longest palindromic subsequence of $s$.

Constraints

• $1 \le n \le 5000$
• $s$ consists only of lowercase English letters.

Subtasks

• For 20 points, $n \le 20$.
• For 30 points, $n \le 500$.
• For 50 points, no additional constraints.

Example 1

5
bbbab

4

Explanation

One longest palindromic subsequence is bbbb.

Example 2

4
cbbd

2

Explanation

One longest palindromic subsequence is bb.

Example 3

6
agbdba

5

Explanation

One longest palindromic subsequence is abdba.