페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#9657
서브태스크

기준 3초 512MB

문제

즐거운 체육 시간이다. 

 

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

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

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

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

 

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

 

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

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


입력

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

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


출력

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

부분문제

번호 점수 조건
#116점

n, v_i ≤ 1000

#223점

a_i = 1

#327점

v_1​,v_2​< ... <v_n

#434점

추가 제약 조건 없음


예제1

입력
3

21

31

11
출력
2

2

2

예제2

입력
4

172

235

114

95
출력
17

23

17

11

예제3

입력
3

1020

1005

10005
출력
10

10

10

출처

COCI 2022/2023 Contest #4 5번

역링크