X. Shortest Travel
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The land of Transportopia consists of $$$n$$$ cities, numbered from $$$1$$$ to $$$n$$$, each located equally spaced on a line. Each city has a single airport, run by a single company.

You are given a string $$$s$$$ of length $$$n$$$, consisting of uppercase Latin letters, where the $$$i$$$-th character denotes which company owns the airport in city $$$i$$$.

In your visit to Transportopia, you are trying to travel from city $$$1$$$ to city $$$n$$$ as quickly as possible. You can take a $$$1$$$ hour bus ride between any two adjacent cities or a $$$1$$$ hour flight between any two cities $$$i$$$ and $$$j$$$, as long as their airports are owned by the same company (i.e. $$$s_i = s_j$$$).

Unfortunately, you can only afford to buy at most one plane ticket. Under these conditions, what is the minimum number of hours it takes to travel from city $$$1$$$ to city $$$n$$$?

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of cities.

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of uppercase Latin letters — the company that owns each city's airport.

Output

Print a single integer — the minimum number of hours it takes to travel from city $$$1$$$ to city $$$n$$$.

Examples
Input
7
ABCDACB
Output
2
Input
5
AAAAA
Output
1
Input
5
YUUKI
Output
4
Input
5
ETHAN
Output
4