题目描述

唐僧师徒四人行至狮驼岭，由于太白金星的警告，唐僧决定让孙悟空先探一探妖怪的动向。

孙悟空探路一共会经过 $n$ 个地点，第 $i$ 个地点的高度是 $h_i$。如果某个地点比它左右相邻的地点都要高，我们就把这个地点称为“山头”。

孙悟空决定在路线上找到所有山头中最中间的一个山头，在这个位置施展法天象地来威慑妖怪。请你帮助他找到这个山头的位置。

聪明的你一定会发现：如果山头的数量是偶数，那么是不存在“最中间”的山头的。此时孙悟空会选择中间两个山头靠左的那一个。

如果你更聪明一些就又会发现，可能出现一个山头都没有的情况。这样孙悟空只能直接返回，此时请输出 $-1$。

输入格式

第一行：一个整数 $n$，表示孙悟空探路经过的地点数；

第二行：$n$ 个整数 $h_1,h_2,...,h_n$，表示每个地点的高度。

输出格式

一个整数数，表示孙悟空选择的山头编号。

样例

11
3 2 4 1 5 5 6 4 8 7 8

7

11
2 3 4 5 4 7 6 9 1 2 1

6

样例 $1$ 解释

在样例 $1$ 中，加粗的位置即为山头：

3 2 4 1 5 5 6 4 8 7 8

在所有山头中，最中间山头高度是 $6$，它是第 $7$ 个山头，因此输出 $7$。

样例 $2$ 解释

在样例 $2$ 中，加粗的位置即为山头：

2 3 4 5 4 7 6 9 1 2 1

在所有山头中，最中间山头有两个，高度分别是 $7,9$，所以选择高度为 $7$ 的山头，它是第 $6$ 个山头，因此输出 $6$。

数据规模与约束

对于 $100\%$ 的数据，$3≤n≤100000，0≤h_i≤10^9$。