Colored Balls: Revisited
Contest: Educational Codeforces Round 135 (Rated for Div. 2)
Difficulty rating: 800
Tags: brute force, greedy, implementation, sortings

The title is a reference to the very first Educational Round from our writers team, Educational Round 18.

There is a bag, containing colored balls. There are $$$n$$$ different colors of balls, numbered from $$$1$$$ to $$$n$$$. There are $$$\mathit{cnt}_i$$$ balls of color $$$i$$$ in the bag. The total amount of balls in the bag is odd (e. g. $$$\mathit{cnt}_1 + \mathit{cnt}_2 + \dots + \mathit{cnt}_n$$$ is odd).

In one move, you can choose two balls with different colors and take them out of the bag.

At some point, all the remaining balls in the bag will have the same color. That's when you can't make moves anymore.

Find any possible color of the remaining balls.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 20$$$) — the number of colors.

The second line contains $$$n$$$ integers $$$\mathit{cnt}_1, \mathit{cnt}_2, \dots, \mathit{cnt}_n$$$ ($$$1 \le \mathit{cnt}_i \le 100$$$) — the amount of balls of each color in the bag.

The total amount of balls in the bag is odd (e. g. $$$\mathit{cnt}_1 + \mathit{cnt}_2 + \dots + \mathit{cnt}_n$$$ is odd).

Output format:
For each testcase, print a single integer — any possible color of the remaining balls, after you made some moves and can't make moves anymore.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, your first and only move can be one of the following:

- take balls with colors $$$1$$$ and $$$2$$$;
- take balls with colors $$$1$$$ and $$$3$$$;
- take balls with colors $$$2$$$ and $$$3$$$.

After the move, exactly one ball will remain. Its color can be $$$3, 2$$$ or $$$1$$$ depending on the move.

In the second testcase, you can't make moves at all — there is only color of balls already. This color is $$$1$$$.

In the third testcase, you can keep removing one ball of color $$$1$$$ and one ball of color $$$2$$$ until there are no more balls of color $$$1$$$. At the end, three balls of color $$$2$$$ remain.

Example input:
3
3
1 1 1
1
9
2
4 7

Example output:
3
1
2

Editorial:
Let's prove that the color with the maximum value of $$$cnt$$$ is one of the possible answers.
Let the color $$$x$$$ have the maximum value of $$$cnt$$$; if there are several such colors, choose any of them. Let's keep taking the balls of two different colors out of the bag without touching the balls of color $$$x$$$ for as long as possible.
After such operations, two cases exist. In one case, only balls of color $$$x$$$ are left — then everything is fine. In other case, there are balls of color $$$x$$$ and some color $$$y$$$ (let $$$cnt_y$$$ be the remaining number of balls of this color). Since initially $$$cnt_x$$$ was one of the maximums, $$$cnt_y \le cnt_x$$$. However, the number of remaining balls is odd, which means $$$cnt_y \ne cnt_x$$$ and $$$cnt_y < cnt_x$$$. Therefore, we can keep taking the balls of colors $$$y$$$ and $$$x$$$ until only balls of color $$$x$$$ are left.