Longest Palindromic Subsequence

Given a string s, your task is to find 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 sequence is a palindrome if it reads the same backwards as forwards.

This problem can be modeled using dynamic programming. A common recurrence relation is given as follows:

\( dp[i][j] = \begin{cases} dp[i+1][j-1] + 2 & \text{if } s[i] = s[j] \\ \max(dp[i+1][j],\,dp[i][j-1]) & \text{otherwise} \end{cases} \)

The base case is that any single character is a palindrome of length 1.

inputFormat

The input consists of a single line containing the string s.

You should read the input from standard input (stdin).

outputFormat

Output a single integer representing the length of the longest palindromic subsequence in the given string. Write the output to standard output (stdout).

## sample

bbbab

4

</p>