Migrated from Lutece 2431 我是音乐小天才

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

钢琴小王子珈伽松捡到一份乐谱，乐谱由 $n$ 个音符构成，他弹奏后很喜欢这首曲子。

作为自负的强迫症患者，他想要在乐谱中某些位置插入音符（也可以一个都不插入）使乐谱从前往后弹奏和从后往前弹奏是一样的曲子。因为他认为对称是音乐必需的美感。

Input

第一行一个整数 $n(1\le n\le 5000)$，代表乐谱的长度。

接下来一行长度为 $n$ 的字符串，每个字符代表一个音符，只包括英文字母和数字。

Output

输出一个整数，表示珈伽松最少需要插入的音符数。

Samples

5
aBcB1

2

Resources

2020 UESTC ICPC Training for Dynamic Programming