Page not loading? Try clicking here.
Placeholder

#9657
Subtask

기준 3s 512MB

Problems

즐거운 체육 시간이다. 

 

체육관에 학생들은 키 순서대로 줄을 서 있다. ​​

체육 선생님은 준비 운동을 위해 기준을 잡고 싶어한다. 

기준이 되는 학생은 ​중앙에 있는 학생이다.

만약 중앙이 되는 학생이 2명 있으면 그 중 키가 더 작은 학생이 기준이 된다. 2명의 키가 같다면 둘 중 아무나 기준이 된다.

 

체육관에 학생들이 들어오기 시작했다.

 

한번에 키가 v_i​인 학생이 a_i명 들어온다.

총 n번 들어올 때, 학생들이 들어올 때마다 기준이 되는 학생의 키를 구하라.


Input

첫 줄에 체육관에 학생들이 들어오는 횟수 n(1 ≤ n ≤ 200,000)이 주어진다.

다음 n줄에 걸쳐 들어오는 학생의 키 v_i​ 와 학생의 수 a_i​ 가 주어진다. (1 ≤ v_i, a_i​​ ≤ 10^9)


Output

n줄에 걸쳐 기준이 되는 학생의 키를 출력한다.


Subtask

# Score Condition
#116

n, v_i ≤ 1000

#223

a_i = 1

#327

v_1​,v_2​< ... <v_n

#434

추가 제약 조건 없음


Example #1

3

2 1

3 1

1 1
2

2

2

Example #2

4

17 2

23 5

11 4

9 5
17

23

17

11

Example #3

3

10 20

100 5

1000 5
10

10

10


Source

COCI 2022/2023 Contest #4 5번

You must sign in to write code.