Vrsta

면접 대비

시간 제한1초메모리 제한1024 MB

요약

매 문장마다 키 v_i인 학생 a_i명이 추가될 때, 줄의 가운데에 서는 학생의 키를 출력한다. 가운데가 둘이면 더 작은 쪽을 택한다.

난이도: 보통10점 중 5점
유형: 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

Domagoj’s favorite school subject is P.E. Every P.E. class starts with warm-up exercises. The teacher has an interesting way of choosing the student who will lead the warm-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 warm-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\_i$ students entering the gym with height $v\_i$ ”. After every statement said by Lovro, Domagoj is interested in the height of the student who will lead the warm-up, if only the students who entered the gym come to P.E. class. Help him answer his questions!

입력

The first line contains the integer $n$ ( $1 ≤ n ≤ 200\\,000$ ), the number of Lovro’s statements.

The following $n$ lines contain two integers $v\_i$ , $a\_i$ ( $1 ≤ v\_i , a\_i ≤ 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.

예제3

예제 1
입력
```
3
2 1
3 1
1 1
```
예상 출력
```
2
2
2
```
예제 2
입력
```
4
17 2
23 5
11 4
9 5
```
예상 출력
```
17
23
17
11
```
예제 3
입력
```
3
10 20
100 5
1000 5
```
예상 출력
```
10
10
10
```