10299: CF EDU - DSU - Step 2 - A. People are leaving
[Creator : ]
Description
$n$ persons are standing at positions $1$ to $n$. You have to perform queries of two types:
- "- x" — the person at position $x$ leaves;
- "? x" — find the nearest person to the right that is still standing.
Input
The first line of the input contains two integers $n, m\ (1≤n,m≤10^6)$ — the number of people and the number of queries.
Next $m$ lines contain queries, one per line. For queries on the leave the line looks like "- x" (1≤x≤n). For queries on the nearest person, the line looks like "? x" (1≤x≤n). It is guaranteed that all the leaving people are distinct.
Output
Output the result of each "?" operation one per line in the corresponding order. If there is no person to the right — output "-1".
Sample 1 Input
5 10
? 1
- 3
? 3
- 2
? 1
? 2
- 4
? 3
- 5
? 3
Sample 1 Output
1
4
1
4
5
-1