P9176 [COCI 2022/2023 #4] Vrsta

Domagoj 最喜欢的课是体育课。每节体育课都以热身运动开始。体育老师有一个有趣的方法来选择带领其他同学做热身运动的学生。学生们按身高从低到高的顺序站成一排，老师会选择站在队伍中间的学生。如果有两个学生在中间，他将选择较矮的那个。例如：如果学生的身高为 $1, 3, 5, 7, 11$，身高为 $5$ 的学生将带领其他同学做热身运动。 Domagoj 记不住他同学的身高。幸运的是，站在他旁边的 Lovro 十分擅长估计他人的身高。他给了 Domagoj $n$ 条信息：「有 $a_i$ 个身高为 $v_i$ 的学生进入了体育馆。」在 Lovro 说完每条信息之后，Domagoj 都对带领其他同学做热身运动的那个同学的身高感兴趣。假定所有进入体育馆的同学都是来上体育课的。请帮他回答他的问题！

第一行一个整数 $n\ (1\le n\le 200\ 000)$，表示 Lovro 的信息条数。 接下来 $n$ 行包含两个整数 $v_i,a_i\ (1\le v_i,a_i\le 10^9)$，表示 Lovro 所给信息中的身高和人数。

输出 $n$ 行，表示在 Lovro 给出第 $i$ 条信息后，对 Domagoj 问题的回答。

|子任务编号| 附加限制| 分值| |:-:|:-:|:-:| | $0$ | 是样例 | $0$ | | $1$ | $n,v_i\le 1000$ | $17$ | | $2$ | $a_1=a_2=\ldots=a_n=1$ | $24$ | | $3$ | $v_1