String Sorting

Arghya BRACU জয়যাত্রা’50 Techfe...
Limits 2s, 512 MB

You'll be given a string $s = s_1s_2.....s_n$ of length $n$ consisting of lowercase english letters and $q$ queries. In each query you'll be given two integers $l$ and $r$, you've to report the minimum number of operations you need to make in order to sort the substring $s_ls_{l+1}.....s_r$. In one operation you can take two adjacent indices and swap the characters.

Input

First line of input contains the string $s (1≤|s|≤10^6)$
Second line of input contains the number of queries $q (1≤q≤10^6)$.
Next $q$ lines contain two integer $l, r (1≤l≤r≤|s|) $ .

Output

For each query output one integer, the minimum number of operations you need to make.

Sample

InputOutput
bcab
3
1 2
2 3
1 4
0
1
3

Note that, you just have to answer how many operation it takes to sort the substring, you are not making any operation in the string. So the original string doesn't change over queries.

Submit

Login to submit.

Statistics

64% Solution Ratio
S_SubrataEarliest, Apr '21
steinumFastest, 0.0s
steinumLightest, 440 kB
mdshadeshShortest, 857B
Toph uses cookies. By continuing you agree to our Cookie Policy.