즐거운 체육 시간이다.

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

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

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

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

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

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

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

기준 timer 3초 memory 512MB

기준 3초 512MB