You'll be given a string of length consisting of lowercase English letters and queries. In each query you'll be given two integers and , you've to report the minimum number of operations you need to make in order to sort the substring . In one operation you can take two adjacent indices and swap the characters.
First line of input contains the string ().
Second line of input contains the number of queries (). Next lines contain two integer , ().
For each query output one integer, the minimum number of operations you need to make.
Input | Output |
---|---|
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.