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