该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Domagoj 最喜欢的课是体育课。每节体育课开始时，老师都会挑选一名同学带领大家做热身运动。 选法是：全班同学按照身高从低到高排成一排，老师选择站在队伍正中间的学生来带领做操。 如果有两个学生正好在中间，则选择较矮的那位。

例如： 若身高为 $1,3,5,7,11$，则第 $3$ 个（身高 $5$）的同学领操。

Domagoj 记不清同学的身高，但他邻座的 Lovro 能猜测每个人的身高分布。 Lovro 给出 $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$），表示身高为 $v_i$ 的学生有 $a_i$ 个。

输出格式

输出 $n$ 行，第 $i$ 行表示 Lovro 提供第 $i$ 条信息后，Domagoj 根据当前信息确定的领操同学身高。

输入输出样例

3
2 1
3 1
1 1

2
2
2

4
17 2
23 5
11 4
9 5

17
23
17
11

3
10 20
100 5
1000 5

10
10
10

数据范围与提示