P17688 [IO 2025 #2] 失物招领处

在整理好公交线路后，市长决定为城市增添一些现代气息：在顿河畔罗斯托夫最西边的列文佐夫卡地区建设高速有轨电车。由于缺乏相关经验，他们决定把电车线路建成一条直线。这样就不需要转弯，基础设施的建设也会更简单。 然而，新的问题出现了：失物招领处应该设在哪里？这个问题比乍看之下更加重要。人们在上下电车时总会遗失东西：购买的商品、背包、钥匙、手机……于是，许多乘客留下了自己的物品，又不得不去寻找它们。 市长知道自己应该关心市民，因此决定把失物招领处设在一个距离其他车站尽可能“近”的车站上。但事情并不简单：有些车站比另一些车站更受欢迎。一个客流较少的车站可能离其他车站更近，却因为到访人数少而不够方便；另一个车站可能稍远，但由于客流更多，反而更合适。 这座城市有史以来最优秀的城市规划实习生提出了一个合理的方法：给每个车站赋予一个受欢迎程度 $p_i$。应该选择一个车站 $i$，使它到其他各车站 $j$ 的距离乘以对应的受欢迎程度 $p_j$ 后，所得总和最小。这样，失物招领处就能尽可能靠近最受欢迎的车站。 具体来说，车站按坐标递增的顺序编号为 $1,2,\ldots,n$，车站 $i$ 的坐标为 $a_i$。你需要找到使下式最小的车站 $i$： $$ \sum_{j\ne i}p_j|a_i-a_j|. $$ 请帮助这位实习生找到答案。

第一行包含一个整数 $n$，表示线路上的车站数量，满足 $2\le n\le3\cdot10^5$。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各车站在直线上的坐标。保证坐标严格递增，任意两个车站的位置不同。 第三行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示各车站的受欢迎程度。 所有 $a_i$ 和 $p_i$ 都是正整数，且不超过 $10^6$。

输出一个整数，表示应该设置失物招领处的车站编号。如果多个车站都能使加权距离总和最小，输出其中编号最小的车站。

符号 $\sum$ 称为求和符号。条件 $j\ne i$ 表示对所有下标不等于 $i$ 的项求和，也就是： $$ \sum_{j\ne i}p_j|a_i-a_j| =p_1|a_i-a_1|+\cdots+p_{i-1}|a_i-a_{i-1}|+p_{i+1}|a_i-a_{i+1}|+\cdots+p_n|a_i-a_n|. $$ 在第一个样例中： - 如果把失物招领处设在车站 $1$，总和为 $3\cdot2+4\cdot4+1\cdot11=33$。 - 如果设在车站 $2$，总和为 $8\cdot2+4\cdot2+1\cdot9=33$。 - 如果设在车站 $3$，总和为 $8\cdot4+3\cdot2+1\cdot7=45$。 - 如果设在车站 $4$，总和为 $8\cdot11+3\cdot9+4\cdot7=143$。 根据相等时选择较小编号的规则，应把失物招领处设在车站 $1$。