Vrsta

면접 대비

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

요약

각 진술마다 키 v_i인 학생 a_i명이 줄에 추가되며, 학생 수가 짝수이면 더 작은 키를 택해 가운데 학생의 키를 출력합니다.

난이도: 보통10점 중 4점
유형: 세그먼트 트리, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

Domagoj가 가장 좋아하는 과목은 체육이다. 체육 수업은 항상 준비운동으로 시작한다. 선생님은 준비운동을 이끌 학생을 특이한 방법으로 고른다. 학생들은 키 순서대로 한 줄로 선다. 선생님은 줄의 가운데에 선 학생을 고른다. 가운데 학생이 두 명이면 키가 작은 쪽을 고른다. 예를 들어 키가 $1$ , $3$ , $5$ , $7$ , $11$ 인 학생들이 있다면 키가 $5$ 인 학생이 준비운동을 이끈다.

Domagoj는 반 친구들의 키를 기억하지 못한다. 옆에는 키를 아주 잘 어림하는 Lovro가 서 있다. Lovro는 Domagoj에게 $n$ 개의 진술을 한다. "키가 $v_i$ 인 학생이 $a_i$ 명 체육관에 들어온다." 진술이 하나 나올 때마다 Domagoj는 체육관에 들어온 학생들만 체육 수업에 왔을 때 준비운동을 이끄는 학생의 키가 궁금하다. 그의 질문에 답하라.

입력

첫 줄에 정수 $n$ ( $1 \le n \le 200\,000$ )이 주어진다. 이는 Lovro의 진술 개수이다. 다음 $n$ 개 줄에는 두 정수 $v_i$ , $a_i$ ( $1 \le v_i, a_i \le 10^9$ )가 주어진다. 이는 Lovro의 진술에서 키가 $v_i$ 인 학생이 $a_i$ 명이라는 뜻이다.

출력

$n$ 개의 줄을 출력한다. $i$ 번째 줄에는 처음 $i$ 개의 진술을 들은 뒤 준비운동을 이끄는 학생의 키를 출력한다.

예제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
```