Cerința

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 ≤ i < j ≤ N, pentru care este adevărată relația Si > Sj.

Date de intrare

Pe prima linie a intrării 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 ≤ N ≤ 200.000
• 1 ≤ Q ≤ 400.000

Exemplu:

Intrare

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

Ieșire

0
5
1
5
0
5