My AC program gives answer "1" to the test:

GTACcAaa
1
1 8

I'm wrong?

I think so, as there is no "t" to pair with the "T" in the input string.

Could you explain me how did you solve this one? My RMQ solution gives WA in test case 41.

Why? My program is incorrect. It gives wrong answers on the test above and on many other tests. It's strange that I've got AC.

But test 41 contains something like this:
AGgTta
1
1 6

Right answer is "1".

I aswered "i think so" trying to say that "your program is incorrect indeed". Sorry. Your code AC is strange for me too.

BTW, really thanks for the test 41 tip. I finally got my AC.