Domagoj’s favorite school subject is P.E. Every P.E. class starts with wa\(rm-up\)
exercises. The teacher has an interesting way of choosing the student who will lead
the wa\(rm-up\). The students stand in a line sorted by their height. The teacher will
choose the student that is standing in the middle of the line. If two students are
in the middle, he will choose the shorter one. For example: if the students have
heights 1 3 5 7 11, the student with height 5 will lead the wa\(rm-up\) exercises.
Domagoj does not remember how tall his classmates are. Luckily, next to him
stands Lovro who is very good at estimating people’s heights. He gives Domagoj \(n\) statements: “There are
\(a@@RISE_MATH_BLOCK_0@@i\)”. After every statement said by Lovro, Domagoj is interested
in the height of the student who will lead the wa\(rm-up\), if only the students who entered the gym come to
P.E. class. Help him answer his questions!

Subtask 1 (19 points): n, \(v_{i} \le 1\,000\)

Subtask 2 (26 points): \(a@@RISE_MATH_BLOCK_0@@n = 1\)

Subtask 3 (29 points): \(v\)\(1 < v\)2 < . . . < v\(n\)

Subtask 4 (36 points): No additional constraints.

The first line contains the integer \(n\) (\(1 \le n \le 200\), 000), the number of Lovro’s statements.
The following \(n\) lines contain two integers \(v@@RISE_MATH_BLOCK_0@@i\) (\(1 \le v\)\(i\), a\(i \le 10^{9}\)), the height and the number of students
in Lovro’s statement.

In the \(i-th\) of \(n\) lines output the answer to Domagoj’s question after \(i\) of Lovro’s statements.

생성자가 기록되지 않았습니다.

출처 COCI 2022/2023 Contest 4