Diversidade Cultural

Uma empresa de turismo oferece passeios marítimos para estrangeiros em duas viagens diárias. Os turistas aguardam a saída das duas embarcações em uma fila, e os $K$ primeiros embarcam no primeiro navio, enquanto que os demais embarcam no segundo.

A diversidade cultural do barco $i$ é determinada pelo número de nacionalidades distintas de seus passageiros. Por exemplo, se a fila é formada por um alemão, dois brasileiros, um canadense e um dinamarquês, isto é, “abbcd”, e $K = 2$, então o primeiro barco tem diversidade $d_1 = 2$ e o segundo barco tem diversidade $d_2 = 3$.

A empresa deseja minimizar a diferença cultural entre os dois barcos, isto é, encontrar um valor $K$ tal que a diferença $d = |d_1 - d_2|$ seja a menor possível. Ajude-os a encontrar este valor, sabendo que cada barco deve levar, no mínimo, um passageiro.

Entrada

A primeira linha da entrada contém o número $N$ ($2\leq N\leq 2\times 10^5$) de passageiros na fila.

A segunda linha contém uma string $S$, onde o $i$-ésimo caractere representa a nacionalidade do $i$-ésimo passageiro da fila. Esta string é composta por $N$ caracteres alfabéticos minúsculos.

Saída

Imprima, em uma linha, o valor de $K$ que minimiza a diferença $d$. Se existir mais de um valor que minimize esta diferença, imprima qualquer um deles.

Exemplo de entrada 1

5
abbcd

Exemplo de saída 1

3

Exemplo de entrada 2

5
abcde

Exemplo de saída 2

2

Exemplo de entrada 3

8
aaaaaaaa

Exemplo de saída 3

1