Seven-Colored Flower#4485
Once upon a time, there was a girl named Zhenya. One day, her mother sent her to the store to buy bagels. On her way, she discovered a magical flower, the Seven-Color Flower, which could grant any wish. Like any little girl, Zhenya wished for many toys, specifically toys. She numbered the spots on her shelf from to and arranged the toys neatly. For each toy, she assigned a "beauty" value, a natural number indicating how beautiful the toy is. Zhenya's friends often visit her. When a girl visits, she specifies two numbers, and . Zhenya then selects the most beautiful toy from the shelf positions between and and gives it to her friend. If a boy visits, he specifies a position and brings a toy with beauty . Zhenya then swaps his toy with the one at position on her shelf. If a girl requests toys from positions where none exist, Zhenya gives her the most beautiful toy she has. If she has no toys left, she outputs O-o-ops. If there are multiple toys with the highest beauty in the range, Zhenya chooses the toy with the smallest position number. If a boy specifies a position with no toy, he simply takes his toy back, and no swap occurs.
The first line contains a single number – the number of toys Zhenya has.
The second line contains numbers representing the beauty of each toy (1 \leq N \leq 10^6, 1 \leq A_i \leq 10^9).
The third line contains the number (1 \leq M \leq 10^5) – the number of Zhenya's friends.
The following lines contain the requests from her friends. If a girl visits, the line starts with g, followed by two numbers and . If a boy visits, the line starts with b, followed by two numbers and .
For each girl, output one number – the beauty of the toy Zhenya will give her, or O-o-ops if she has no toys left.
Example 1