Minimum Removals to Palindrome

You are given a string of length n. Your task is to determine the minimum number of characters that need to be removed from the string so that the remaining characters form a palindrome.

A palindrome is a string that reads the same forwards and backwards. One way to solve this problem is by finding the length of the longest palindromic subsequence (LPS) in the string. The minimum number of removals required is given by the formula: \( n - LPS \).

For example, if the string is "abc" with n = 3, the longest palindromic subsequence is either "a", "b", or "c", each of length 1. Therefore, the minimum number of removals is \(3 - 1 = 2\).

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains an integer n, representing the length of the string.
• The second line contains the string s composed of lowercase letters.

outputFormat

Output a single integer representing the minimum number of removals required to convert the given string into a palindrome. The output should be written to standard output (stdout).

## sample

3
abc

2

</p>