Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

String Sorting

By Arghya · Limits 2s, 512 MB

You'll be given a string s=s1s2.....sns = s_1s_2.....s_n of length nn consisting of lowercase english letters and qq queries. In each query you'll be given two integers ll and rr, you've to report the minimum number of operations you need to make in order to sort the substring slsl+1.....srs_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(1s106)s (1≤|s|≤10^6)
Second line of input contains the number of queries q(1q106)q (1≤q≤10^6).
Next qq lines contain two integer l,r(1lrs)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.

    Discussion

    Statistics


    0% Solution Ratio

    Submit

    Login to submit