Carrossel de fichas

Time limit: 3000 msMemory limit: 256 MB

Há $n$ fichas em um círculo, numeradas de $1$ a $n$ no sentido horário. A ficha $i$ contém a letra $s_i$ .

Escolha uma posição inicial $p$ e leia exatamente $n$ fichas no sentido horário, começando em $p$ . Uma pilha, inicialmente vazia, é atualizada a cada ficha lida:

Se a pilha não está vazia e a letra no topo é igual à letra lida, retire a ficha do topo e descarte a ficha lida.
Caso contrário, coloque a ficha lida no topo.

Uma posição inicial é válida se a pilha termina vazia. O pico dessa posição é o maior número de fichas simultaneamente na pilha durante a leitura.

Determine o menor pico entre as posições válidas e quantas posições atingem esse pico. Posições diferentes contam separadamente, mesmo quando produzem a mesma sequência de letras.

Input

A primeira linha contém um inteiro $n$ ( $1 \le n \le 200\,000$ ).

A segunda linha contém uma string $s$ de comprimento $n$ , formada por letras maiúsculas de A a Z.

Output

Imprima dois inteiros: o menor pico e a quantidade de posições que o atingem. Se nenhuma posição for válida, imprima -1 0.

Samples

Sample 1

Input

4
ABBA

Output

1 2

As posições $2$ e $4$ produzem, respectivamente, BBAA e AABB, ambas com pico $1$ . As outras duas posições têm pico $2$ .

Sample 2

Input

4
ABAB

Output

-1 0

Nenhuma posição deixa a pilha vazia.

Sample 3

Input

2
AA

Output

1 2

As duas posições são contadas separadamente.