← 返回题目列表

Codeforces · 1433/C

C. 占主导地位的食人鱼

中文机器翻译题面 查看原题

水族馆里有 $$$n$$$ 尺寸的食人鱼,尺寸为 $$$a_1, a_2, \ldots, a_n$$$。食人鱼按照它们在水族馆中的生活顺序从左到右编号。

贝尔兰州立大学的科学家们想要找出水族馆中是否存在占主导地位的食人鱼。如果食人鱼可以吃掉水族馆中的所有其他食人鱼(当然除了它自己),则该食人鱼被称为优势食人鱼。其他食人鱼不会做任何事,而占主导地位的食人鱼会吃掉它们。

由于水族箱又窄又长,食人鱼在一次移动过程中只能吃掉相邻的食人鱼之一。食人鱼可以根据需要(或可以)进行尽可能多的动作。更准确地说:

- 如果食人鱼 $$$i-1$$$ 存在并且 $$$a_{i - 1} < a_i$$$,则食人鱼 $$$i$$$ 可以吃掉食人鱼 $$$i-1$$$。
- 如果食人鱼 $$$i+1$$$ 存在并且 $$$a_{i + 1} < a_i$$$,则食人鱼 $$$i$$$ 可以吃掉食人鱼 $$$i+1$$$。

当食人鱼 $$$i$$$ 吃掉一些食人鱼时,它的大小会增加一倍($$$a_i$$$ 变为 $$$a_i + 1$$$)。

你的任务是在水族馆中找到任何占主导地位的食人鱼,或者确定是否没有这样的食人鱼。

请注意,您必须找到任何(恰好一个)占主导地位的食人鱼,而不必找到所有它们。

例如,如果 $$$a = [5, 3, 4, 4, 5]$$$,则第三个食人鱼可以占主导地位。考虑其移动顺序:

- 食人鱼吃掉了第二个食人鱼,$$$a$$$ 变成 $$$[5, \underline{5}, 4, 5]$$$ (下划线的食人鱼是我们的候选者)。
- 食人鱼吃掉了第三个食人鱼,$$$a$$$ 变成 $$$[5, \underline{6}, 5]$$$。
- 食人鱼吃掉了第一只食人鱼,$$$a$$$ 变成了 $$$[\underline{7}, 5]$$$。
- 食人鱼吃掉了第二个食人鱼,$$$a$$$ 变成了 $$$[\underline{8}]$$$。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 水族馆中食人鱼的数量。测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个食人鱼的大小。

保证$$$n$$$之和不超过$$$3 \cdot 10^5$$$ ($$$\sum n \le 3 \cdot 10^5$$$)。

输出

对于每个测试用例,打印答案:如果水族馆中没有优势食人鱼,则打印答案:-1,否则打印任何优势食人鱼的索引。如果有多个答案,您可以打印任何一个。

示例

输入 #1

6
5
5 3 4 4 5
3
1 1 1
5
4 4 3 4 4
5
5 5 4 3 2
3
1 1 2
5
5 4 3 5 5

输出 #1

3
-1
4
3
3
1

注意

示例的第一个测试用例在问题陈述中进行了描述。

在示例的第二个测试用例中,水族箱中不存在占优势的食人鱼。

在示例的第三个测试用例中,第四个食人鱼可以先吃掉左边的食人鱼,水族箱变成$$$[4, 4, 5, 4]$$$,然后它可以吃掉水族箱中的任何其他食人鱼。