## Algorithm

Problem Name: 2 AD-HOC - beecrowd | 1615

# Insatisfaction on Elections

Timelimit: 1

An election was made in a small town of M citizens, where there were N candidates. People would write the candidate number in a piece of paper, and then they put it in a closed box.

At the end of the election, if a candidate receives a quantity strictly greater than 50% of the votes, he is considered the winner. Otherwise a second round of elections will happen.

As the manual counting process is very slow, you must write an algorithm that decides whose candidate is the winner or if none of them received enough votes and a second round is needed.

## Input

The first line contains an integer T (T ≤ 100) indicating the number of test cases.

For each test case, on the first line you will have the integers N (1 ≤ N ≤ 10) and M. On the following line, M (1 ≤ M ≤ 103* or 1 ≤ M ≤ 5*104**) integers will follow separated by spaces, indicating the candidate that each citizen voted for, it is, the number that was writen in each piece of paper inside the closed box.

*For around 90% of the cases;

**For the other cases.

## Output

For each test case, print the winning candidate, or -1 in the case of a second round of elections.

 Sample Input Sample Output 3 2 3 1 1 2 2 5 1 2 2 1 2 3 4 1 2 3 1 1 2 -1

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define MAXV 200100

using namespace std;

typedef vector<int> vi;
typedef pair < int, int> ii;
typedef long long int64;

typedef pair < int, string> is;

{
bool minus = false;
int result = 0;
char ch;
ch = getchar_unlocked();
while (true) {
if (ch == '-')
break;
if (ch >= '0' && ch  < = '9')
break;
ch = getchar_unlocked();
}
if (ch == '-')
minus = true;
else
result = ch - '0';
while (true) {
ch = getchar_unlocked();
if (ch  <  '0' || ch > '9')
break;
result = result * 10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}

int main()
{
ios::sync_with_stdio(false);
int a, b, c, t;
while (t--) {
unordered_map < int, int> election;
for (int i = 0; i  <  b; i++) {
if (election.count(c))
election[c]++;
else
election.insert(mp(c, 1));
}
unordered_map < int, int>::iterator it;
int winner = 0, count = 0;
for (it = election.begin(); it != election.end(); it++) {
if (it->second > count) {
count = it->second;
winner = it->first;
}
}
if (count > b / 2)
cout << winner << endl;
else
cout << -1 << endl;
}
return 0;
}
``````
Copy The Code &

Input

cmd
3
2 3
1 1 2
2 5
1 2 2 1 2
3 4
1 2 3 1

Output

cmd
1
2
-1