Bit Shark

Time limit1sMemory limit128 MB

Summary

Find the length of the string left after repeatedly deleting the second half of any even-length palindrome, choosing deletions to maximize bits eaten.

Level: Medium6 of 10
Topics: String, Greedy, Dynamic programming
Solved: No attempts yet

Problem

The Bit Shark (Bitonis Appetitus) is a rare creature that feeds on binary strings. Its staple food is even-length palindromes: contiguous substrings of even length that read the same left to right as right to left.

After choosing a palindrome, the shark eats only its second half. The eaten characters disappear and the two remaining sides join together immediately. For example, in the string 010011 the shark may choose the palindrome 1001; it eats only the second half 01, so the string 0101 is left behind.

The sharks are extremely intelligent, so they always pick palindromes so as to eat as many bits as possible in total. The shark keeps eating until no even-length palindrome remains, which makes the length of the leftover string as small as possible.

For a given binary string, write a program that determines the length of the string that remains after the bit shark's meal.

Input

The first line contains one integer $n$ ( $1 \le n \le 100$ ), the length of the string.

The second line contains a string of length $n$ made of the characters 0 and 1.

Output

Print a single integer: the number of bits that remain in the binary string after the shark has finished eating.

Examples3

Example 1
Input
```
6
100110
```
Expected output
```
2
```
Example 2
Input
```
4
1001
```
Expected output
```
2
```
Example 3
Input
```
4
0101
```
Expected output
```
4
```