题目描述
Problem Description
Domagoj's favorite class is physical education. Each PE class begins with a warm-up session. The PE teacher has an interesting method for selecting the student who leads the warm-up. The students line up in order of increasing height, and the teacher chooses the student in the middle of the line. If there are two students in the middle, he chooses the shorter one. For example, if the students' heights are $1, 3, 5, 7, 11$, the student with height $5$ will lead the warm-up.
Domagoj cannot remember his classmates' heights. Fortunately, Lovro, who stands next to him, is very good at estimating heights. He provides Domagoj with $n$ pieces of information: "There are $a_i$ students with height $v_i$ entering the gym." After each piece of information from Lovro, Domagoj is curious about the height of the student who will lead the warm-up. Assume all students entering the gym are there for the PE class. Please help him answer his questions!
Input Format
The first line contains an integer $n\ (1\le n\le 200\ 000)$, representing the number of pieces of information from Lovro.
The next $n$ lines each contain two integers $v_i, a_i\ (1\le v_i, a_i\le 10^9)$, indicating the height and the number of students with that height according to Lovro's information.
Output Format
Output $n$ lines, each representing the answer to Domagoj's question after the $i$-th piece of information from Lovro.
Sample Input and Output
Input Sample #1
3
2 1
3 1
1 1
Output Sample #1
2
2
2
Input Sample #2
4
17 2
23 5
11 4
9 5
Output Sample #2
17
23
17
11
Input Sample #3
3
10 20
100 5
1000 5
Output Sample #3
10
10
10
Notes/Hints
| Subtask Number | Additional Constraints | Score |
|---|---|---|
| $0$ | Sample cases | $0$ |
| $1$ | $n, v_i \le 1000$ | $17$ |
| $2$ | $a_1 = a_2 = \ldots = a_n = 1$ | $24$ |
| $3$ | $v_1 < v_2 < \ldots < v_n$ | $26$ |
| $4$ | No additional constraints | $33$ |
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分