inversiuni

Cerință

Fie un șir de caractere $S$, format din litere mici ale alfabetului englez, indexat de la $1$. Trebuie să răspundeți la $Q$ query-uri de forma $x, y$ - calculați câte inversiuni se află în intervalul $[x, y]$. O inversiune este o pereche de indici $(i, j)$, $1 \leq i < j \leq N$, pentru care este adevărată relația $S_i > S_j$.

Date de intrare

Pe prima linie din intrare se află un număr natural $N$ reprezentând dimensiunea șirului. Pe a doua linie se află șirul de caractere $S$. Pe a treia linie se află $Q$, reprezentând numărul de query-uri, iar pe următoarele $Q$ linii se află câte două numere naturale, separate printr-un spațiu, care reprezintă un query.

Date de ieșire

Se vor afişa, pe linii diferite, $Q$ numere naturale reprezentând răspunsurile pentru fiecare query.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$;
• $1 \leq Q \leq 400 \ 000$.
• Subtask $1$ ($10$p): $N \leq 100$;
• Subtask $2$ ($20$p): $N \leq 1 \ 000$;
• Subtask $3$ ($40$p): $N \leq 10 \ 000$;
• Subtask $4$ ($30$p): Fără alte restricții.

Exemplul 1

stdin

7
yjiknyy
6
5 7
1 5
2 6
1 6
6 7
1 5

stdout

0
5
1
5
0
5

Exemplul 2

stdin

10
dvoeikwnuw
10
1 7
5 7
1 2
3 8
4 6
1 6
2 7
3 3
2 3
6 9

stdout

7
0
0
5
0
7
7
0
1
2