题目描述

如果在长度为 $m$ 的整数数组 $arr$ 中 超过一半 的元素值为 $x$，那么我们称 $x$ 是 支配元素 。

给你一个下标从 1 开始长度为 $n$ 的整数数组 $arr$ ，数据保证它含有一个 支配元素。

你需要在下标 $i$ 处将 $arr$ 分割成两个数组 $arr[1, ..., i]$ 和 $arr[i + 1, ..., n]$ ，如果一个分割满足以下条件，我们称它是 合法 的：

• $1 <= i <= n$
• $arr[1, ..., i]$ 和 $arr[i + 1, ..., n]$ 的支配元素相同。

这里， $arr[i, ..., j]$ 表示 $arr$ 的一个子数组，它开始于下标 $i$ ，结束于下标 $j$ ，两个端点都包含在子数组内。特别地，如果 $j < i$ ，那么 $arr[i, ..., j]$ 表示一个空数组。

请你输出一个 合法分割 的 最小 下标。如果合法分割不存在，输出 $-1$ 。

输入格式

第一行一个整数 表示 $m$

第二行 $m$ 个空格隔开的整数，表示 $arr$ 数组中的元素。

输出格式

一个整数，表示一个 合法分割 的 最小 下标。如果合法分割不存在，输出 $-1$ 。

样例

样例 1：

4
1 2 2 2

3

解释：

我们将数组在下标 3 处分割，得到 [1,2,2] 和 [2] 。

数组 [1,2,2] 中，元素 2 是支配元素，因为它在数组中出现了 2 次，且 2 * 2 > 3 。

数组 [2] 中，元素 2 是支配元素，因为它在数组中出现了 1 次，且 1 * 2 > 1 。

两个数组 [1,2,2] 和 [2] 都有与 arr 一样的支配元素，所以这是一个合法分割。

下标 3 是合法分割中的最小下标。

样例 2：

10
2 1 3 1 1 1 7 1 2 1

5

解释： 我们将数组在下标 5 处分割，得到 [2,1,3,1,1] 和 [1,7,1,2,1] 。

数组 [2,1,3,1,1] 中，元素 1 是支配元素，因为它在数组中出现了 3 次，且 3 * 2 > 5 。

数组 [1,7,1,2,1] 中，元素 1 是支配元素，因为它在数组中出现了 3 次，且 3 * 2 > 5 。

两个数组 [2,1,3,1,1] 和 [1,7,1,2,1] 都有与 arr 一样的支配元素，所以这是一个合法分割。

下标 5 是所有合法分割中的最小下标。

样例 3：

7
3 3 3 3 7 2 2

-1

解释：没有合法分割。

提示：

• $1 <= m <= 10^5$
• $1 <= arr[i] <= 10^9$
• $arr$ 有且只有一个支配元素。

来源

leetcode.cn:2780