🐰🐱 题目描述

在兔猫信奥学院的地下宝藏洞中，埋藏了一条由无数小石块和一颗唯一的巨石组成的长廊。所有普通石块的重量都相同，只有那颗巨石重量最大。小兔和小猫没有权力直接称重每块石头，只能借助加菲老师提供的时空秤（ArrayReader 接口），它可以比较任意两个连续石块区间的总体重量：

• compareSub(l, r, x, y)：比较区间 ([l..r]) 与 ([x..y]) 的重量和，返回
  • 1 如果 (\sum_{i=l}^r !arr[i]) 大于 (\sum_{i=x}^y !arr[i])；
  • 0 如果两者相等；
  • −1 如果小于。
• length()：返回石块总数 (n)。

加菲老师说：“在最多 20 次比较内，你必须找到那颗巨石的下标（0 起始）！”小兔想出“二分分区，快速排除”，小猫点头称妙。

📥 输入格式

第一行：整数 n  
第二行：n 个正整数 arr[0..n-1]

• \(2 \le n \le 5\times10^5\)
• \(1 \le arr[i] \le 100\)
• 除了一个最大的元素外，其他所有 arr[i] 完全相同；
• 你不得直接访问 arr[i]，只能通过模拟的 ArrayReader.get 和 compareSub 来操作。

📤 输出格式

输出一个整数：巨石的下标（0 到 n−1）

💡 输入输出样例

样例 1

8
7 7 7 7 10 7 7 7

4

样例 2

3
6 6 12

2

📊 数据范围

• 石块数目 \(n\le5\times10^5\)
• 普通石块重量相同，均在 ([1,100])
• 最多调用 compareSub 20 次
• 要求总时间复杂度 (O(\log n))