Unique Bid Auction

Let's simplify this game a bit. Formally, there are $n$ participants, the $i$ -th participant chose the number $a_{i}$ . The winner of the game is such a participant that the number he chose is unique (i. e. nobody else chose this number except him) and is minimal (i. e. among all unique values of $a$ the minimum one is the winning one).

Your task is to find the index of the participant who won the game (or -1 if there is no winner). Indexing is $1$ -based, i. e. the participants are numbered from $1$ to $n$ .

You have to answer $t$ independent test cases.

Input

The first line of the input contains one integer $t$ ( $1 \leq t \leq 2 \cdot 10^{4}$ ) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ( $1 \leq n \leq 2 \cdot 10^{5}$ ) — the number of participants. The second line of the test case contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq n$ ), where $a_{i}$ is the $i$ -th participant chosen number.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^{5}$ ( $\sum n \leq 2 \cdot 10^{5}$ .

Output

For each test case, print the answer — the index of the participant who won the game (or -1 if there is no winner). Note that the answer is always unique.

Example

Input

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

Output

-1
2
4
1
2
-1

Solution

#include <bits/stdc++.h>
using namespace std;

int main()
{

int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
map<int, int> memo, pos;
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
memo[a]++;
pos[a] = i;
}
int ans = -1;
for (auto [num, cnt]: memo)
{
if (cnt == 1)
{
ans = pos[num] + 1;
break;
}
}
cout << ans << endl;
}
return 0;
}

Comments