← 返回题目列表

Codeforces · 733/B

B. 游行

中文机器翻译题面 查看原题

很快伯兰德就会举行一场战胜外星入侵者的游行。不幸的是,所有士兵都在战争中丧生,现在军队由全新的新兵组成,其中许多人甚至不知道应该从哪条腿开始行军。平民百姓也不太了解新兵从哪条腿开始行军,因此重要的是有多少士兵步调一致地行军。

共有n支纵队参加阅兵,第i纵队由黎兵组成,从左腿开始行进,里士兵从右腿开始行进。

阅兵的美观度通过以下公式计算:如果L是从左腿开始行进的士兵总数,R是从右腿开始行进的士兵总数,那么美观度就等于|L - R|。

你只能选择一个纵队,并告诉该纵队中的所有士兵切换出发腿,即该纵队中从左腿开始行军的每个人现在都从右腿开始行军,反之亦然。形式上,您可以选择不超过一个索引 i 并交换值 li 和 ri。

找到该列的索引,使得其中士兵切换起始腿可以最大化游行的美观度,或者确定,没有这样的操作可以增加当前的美观度。

输入

第一行包含单个整数 n (1 ≤ n ≤ 105) — 列数。

接下来的 n 行包含整数对 li 和 ri (1 ≤ li, ri ≤ 500) – 第 i 列中分别从左腿或右腿开始行军的士兵数量。

输出

打印单个整数 k — 士兵需要改变开始行军的那一列的编号,如果已经达到最大美感,则打印 0。

考虑列按照输入数据中给出的顺序从 1 到 n 编号。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

3
5 6
8 9
10 3

输出 #1

3

输入 #2

2
6 5
5 6

输出 #2

1

输入 #3

6
5 9
1 3
4 8
4 5
23 54
12 32

输出 #3

0

注意

在第一个示例中,如果您不下令改变支线,则从左支线开始行进的士兵数量将等于 5 + 8 + 10 = 23,从右支线开始行进的士兵数量为 6 + 9 + 3 = 18。在这种情况下,游行的美丽程度将等于 |23 - 18| = 5。

如果您下令将支线更改为第三纵队,那么从左支线行军的士兵人数将等于 5 + 8 + 3 = 16,从右支线行军的士兵人数为 6 + 9 + 10 = 25。在这种情况下,美感等于 |16 - 25| = 9。

下达另一个命令是不可能达到更大的美丽的。因此,可以达到的最大美感是9。