QMAX3VN - Giá trị lớn nhất 3

no tags 

Following the journey to explore the real power of special data stuctures, two adventurers pirate and duyhung123abc continued to find new challenges with new more and more complicated problems. But what they earned was unremarkable. Being tired and stucked, they decided to review the problems they had solved to see what they had had so far. Suddenly, a mysterious light came to their mind: "why not combine some of them into one !". And here, QMAX3VN was born, as natural as the way fire had come to humankind.

It is said that in a morning at a military camp. All soldiers were gathering in a line to prepare for morning excercises. But the problem was they did not get up simultaneously. The line was initially empty. After sometime, a soldier got up and ran hurrily to join the line. Also, each of them liked to stand near their friends so they would elbow themselves to some position of the current line. What a messy and unacceptable scene for a military camp! The soldiers knew what they had done and were ready to be punished. The strict commander decided to give them a lesson. Everytime he gave an order(x,y), all soldiers in the line had to say loudly the height of the highest man among those were standing from position x to position y. Orders were made continuously since the first soldier entered the line. Punishment was waiting for whom would carried out the order incorrectly. The yard was full of worry from young soldiers. They really needed help !

Input

The input contains several lines:

  • Line 1 : An integer n (1 ≤ n ≤ 100000): The number of events occuring in that morning.
  • Line 2 to line n+1: Each line is one of the following two events:
    • A x y : A soldier with height x had just entered the line and elbowed himself into the position between position y-1 and position y of the line (-109 ≤ x ≤ 109; 1 ≤ y ≤ k+1 , k denotes the number of soldiers in the line right before this soldier came).
    • Q x y : An order of the commander. Find the height of the highest man among those were standing from position x to position y of the line (1 ≤ x ≤ y ≤ k , k denotes the number of soldiers was currently in the line).

 

Output

The output contains several lines:

  • For each order of the commander, write in one line the number all soldiers had to say loudly.

 

Example

Input:
10
A 1 1
A 2 2
Q 1 2
A 3 1
A 4 3
Q 2 4
A 5 2
Q 2 3
A 6 3
Q 1 4

Output:
2
4
5
6


hide comments
amaroq: 2012-01-04 19:14:52

Is it possible to give this problem an English title?

Tony Beta Lambda: 2012-01-04 19:14:52

Yes, in fact it's because there is improper linefeed, I guess it's something like "\r\n".
You may use a loop to eliminate them if you insist to read with getchar(). I did so and got AC.

Last edit: 2009-08-08 13:43:18
Hayk Saribekyan: 2012-01-04 19:14:52

Don't use getchar() to read 'A' and 'Q'. Otherwise you'll get RE's like me. :)

Tony Beta Lambda: 2012-01-04 19:14:52

Large input/output data, be careful using cin and cout; use printf and scanf instead!


Added by:khanhptnk
Date:2009-05-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource:Sưu tầm