Problem Statement

You are given ~n~ queries, each of the following form, either:

• ~\text{SEARCH }x~ where ~x~ is some integer, or
• ~\text{INSERT }x~ where ~x~ is some integer Imagine you start with an empty collection of numbers. When you see ~\text{INSERT }x~ you should add ~x~ to your collection of numbers. Every time you see ~\text{SEARCH } x~ you should determine the first thing less than or equal to ~x~ in your collection of numbers. ## Input Format

Your first line will contain ~n~. Your next ~n~ lines will contain one query each.

Output Format

For each ~\text{SEARCH } x~ query you should output the first thing less than or equal to ~x~ in your current collection of numbers. If there is nothing less than or equal to ~x~, output ~-1~.

Constraints

• ~1 \leq n \leq 10^5~
• ~-10^9 \leq a_i \leq 10^9~ ## Sample Cases

Input 1

7
INSERT 10
SEARCH 9
INSERT 3
INSERT 4
INSERT 8
SEARCH 3
SEARCH 7

Output 1

-1
3
4