BST Problem

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

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

-1
3
4