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\le n\le {10}^5$
• $-{10}^9\le a_i\le {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