🐰🐱 题目描述

在兔猫信奥学院的宝石走廊中，陈列着一排晶莹剔透的宝石。除了有一颗独一无二的魔法宝石外，其他宝石都成双成对地摆放。小兔和小猫奉加菲老师之令，需要在浩瀚宝石中找到这颗唯一的魔法宝石。

加菲老师说：“已知宝石从左到右的编号是非严格升序排列的（相邻成对，唯独魔法宝石只出现一次）。走廊很长，你必须在 \(O(\log n)\) 时间内找出魔法宝石的下标，且只能使用常数空间。”

📥 输入格式

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

• \(1 \le n \le 10^5\)，且 n 为奇数
• \(0 \le gems[i] \le 10^5\)
• gems 已按非严格升序排列，且只有一个元素出现一次，其余每个元素恰出现两次

📤 输出格式

输出一个整数：魔法宝石在 gems 数组中的下标（0 起始）

💡 输入输出样例

样例 1

9
1 1 2 3 3 4 4 8 8

2

魔法宝石编号 2 只出现一次，下标为 2。

样例 2

7
3 3 7 7 10 11 11

4

魔法宝石编号 10 独一无二，下标为 4。

📊 数据范围

• 序列长度 \(n\) 最多 $10^5$（且为奇数）
• 元素值范围 $[0,10^5]$
• 时间复杂度要求 $O(\log n)$，空间复杂度要求 $O(1)$