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

#9657
서브태스크

기준 3s 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

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


출처

COCI 2022/2023 Contest #4 5번
로그인해야 코드를 작성할 수 있어요.