1557: ACM脱单大法

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：2 解决：11

题目描述
        众所不周知！名字笔画为37笔的学长有了女朋友却谁也不知道，我们姑且叫这个学长的名字为撩妹大湿。但是撩妹大湿总是跟c+++创始人走的很近，每天搂搂抱抱不成体统！于是就被撩妹大湿的女朋友给知道了，但是呢，撩妹大湿的女朋友是一个热爱画画的温柔又可爱的女子，于是她决定把撩妹大湿大卸两块，没错是两块！！


        撩妹大湿呢，他的长度是n，并且每个单位长度都有一个相应的重量，他的小女朋友希望将撩妹大湿切成两部分，第一部分重量最大的单位长度和重量最小的单位长度分别要与第二部分重量最大的单位长度和重量最小的单位长度要相等，并且尽量让第一部分长度最短。


由于出题人怕你们看不懂题，所以这个题又可以这样说：
给你一个长度为n的序列a，a[1],a[2],a[3]......a[n-1],a[n]，让你找到一个下标x，使得[1,x],(x,n]这两个区间的最大最小值相同（注意第一段区间是左闭右闭的，第二段区间是左开右闭的）。
可能会存在多个符合题目要求的下标x，请输出最小的x。（下标从1-n）
如果不存在这样的x，请输出-1

输入

第一行一个T，代表有T组样例
接下来T组
每一组第一行一个n，代表序列长度
第二行n个数，a[1],a[2],a[3]......a[n-1],a[n]。


a[i]在int范围内
T＜=100
2＜=n＜=1e5

输出

一个x，意义如题目所描述
可能存在多个答案，请输出最小的x（x<n）

样例输入 复制 

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

样例输出 复制 

2
-1

提示

第一组样例中，符合条件的区间为下面两个
这样划分区间
[1,2](2,5]   前者区间的最大最小值=后者区间的最大最小值
[1,3](3,5]   前者区间的最大最小值=后者区间的最大最小值
2比3小，故输出2
第二组样例中我们找不到这个x值
所以输出-1

来源/分类