CF733B Parade

不久之后，Berland 将举行一次击败外星入侵者的胜利阅兵。不幸的是，所有士兵都在战争中牺牲了，现在的军队全部由新兵组成，其中许多人甚至不知道该从哪条腿开始行进。平民百姓同样不太清楚新兵们应该用哪条腿起步，因此大家只关心有多少士兵能步伐一致。 将有 $n$ 个方阵参加阅兵，第 $i$ 个方阵有 $l_i$ 名士兵从左腿起步，有 $r_i$ 名士兵从右腿起步。 阅兵的美丽度按如下公式计算：设 $L$ 为所有方阵中从左腿起步的士兵总数，$R$ 为所有方阵中从右腿起步的士兵总数，则美丽度等于 $|L-R|$。 你最多可以选择一个方阵，命令该方阵内的所有士兵交换起步的腿，也就是说，所有从左腿起步的士兵将改为从右腿起步，所有从右腿起步的士兵改为从左腿起步。形式上，你可以选择至多一个下标 $i$，将 $l_i$ 和 $r_i$ 的数值交换。 请找出应选择哪一列方阵进行交换（或不做操作），才能使阅兵的美丽度最大化。如果无法通过操作提高当前的美丽度，则输出 $0$。

第一行包含一个整数 $n$（$1\leq n\leq 10^5$）——方阵的数量。 接下来 $n$ 行，每行两个整数 $l_i$ 和 $r_i$（$1\leq l_i,r_i\leq 500$），表示第 $i$ 个方阵中从左腿和右腿起步的士兵人数。

输出一个整数 $k$，表示应让第 $k$ 个方阵内的士兵交换起步的腿；如果无需交换即可达到最大美丽度，输出 $0$。 假设方阵按照输入顺序编号，从 $1$ 到 $n$。 如果有多个答案，输出其中任意一个即可。

在第一个样例中，如果不进行任何腿的交换，所有从左腿起步的士兵数量为 $5+8+10=23$，从右腿起步的士兵数量为 $6+9+3=18$。此时美丽度为 $|23-18|=5$。 如果将第三个方阵交换起步腿，则左腿起步的总人数变为 $5+8+3=16$，右腿起步的人数为 $6+9+10=25$。此时美丽度为 $|16-25|=9$。 无法通过对其他方阵进行操作获得更高的美丽度。所以最大可获得的美丽度为 $9$。 由 ChatGPT 5 翻译