Scrabble

Cerință

Matei joacă o variantă specială de Scrabble. El are în inventar un șir de $N$ litere mici ale alfabetului englez, așezate într-o ordine fixă.

La o mutare, Matei poate alege o subsecvență din inventar, adică literele aflate între două poziții alese $i$ și $j$, cu $1 \le i \le j \le N$. Scorul obținut depinde de cât de dezechilibrate sunt frecvențele literelor din subsecvența aleasă.

Se consideră un șir $S$ de lungime $N$, format doar din litere mici ale alfabetului englez.

Pentru o subsecvență nevidă $T$, definim $fr[x]$ ca fiind numărul de apariții ale literei $x$ în $T$.

Notăm cu $D(T)$ mulțimea literelor distincte care apar în $T$.

Dacă $T$ conține o singură literă distinctă, atunci definim:

Altfel, definim:

Cu alte cuvinte, $dif(T)$ este diferența dintre frecvența celei mai dese litere din $T$ și frecvența celei mai rare litere care apare în $T$. Literele care nu apar în $T$ nu sunt luate în considerare.

De exemplu, pentru $T = abbccc$, avem:

Astfel,

Pentru $T = aaaa$, există o singură literă distinctă, deci:

Pentru fiecare pereche de poziții $i$ și $j$, cu $1 \le i \le j \le N$, notăm cu $S[i \dots j]$ subsecvența lui $S$ care începe la poziția $i$ și se termină la poziția $j$.

Cerința este să determinați scorul maxim pe care îl poate obține Matei alegând o subsecvență a șirului, adică valoarea:

Date de intrare

Prima linie conține numărul întreg $N$, lungimea șirului.

A doua linie conține șirul $S$, format din $N$ litere mici ale alfabetului englez.

Date de ieșire

Afișați un singur număr întreg, reprezentând scorul maxim care poate fi obținut alegând o subsecvență nevidă a șirului $S$.

Restricții și precizări

• $1 \le N \le 10^5$
• Șirul $S$ conține doar litere mici ale alfabetului englez, adică litere de la $a$ la $z$
• Alfabetul are $26$ de litere

Subtaskuri și punctaje

Exemplu

stdin

7
abbbbca

stdout

3

Explicație

Matei poate alege subsecvența $abbbb$.

În aceasta avem:

Prin urmare, $dif(abbbb) = 4 - 1 = 3$. Acesta este scorul maxim care poate fi obținut.