Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Matchstick Man

By saif_sust · Limits 1s, 512 MB

Are you familiar with Matchstick Art ? Well.. you make different kinds of objects with matchsticks. Once upon a time there lived a man in Sylhet, who was very good at Matchstick Art . He became so famous around the world, that he came to be known as the Matchstick Man .

One day after building a beautiful object with matchsticks, he had some matchsticks left. He wanted to use these matchsticks to build a polygon. Now as the Matchstick Man does not like wasting matchsticks, he wanted to use maximum number of matchsticks to build the polygon. He soon discovered that he can use all the matchsticks and build the polygon, because all matchsticks are of same length. He wondered what would happen if the matchsticks were of different lengths. As, he is not very good at programming he came to a student of SUST CSE with that problem. You are given the same problem.

Given the number of matchsticks (N) and their lengths, you have to find the maximum number of matchsticks you can use to make a polygon with area greater than zero (non-degenerate).

Input

Input starts with an integer T (T ≤ 30) denoting the number of test cases.

Each test case starts with an integer N (1 ≤ N ≤ 105), the number of matchsticks. Next line contains N 32-bit integers denoting the length of the matchsticks.

Output

For each case, print the maximum number of matchsticks you can use from the given matchsticks to make a non-degenerate polygon in a single line. If it is impossible to make any non-degenerate polygon print “IMPOSSIBLE” without the quotes.

Sample

InputOutput
3
4
1 4 2 3
3
1 3 2
6
2 50 3 1 5 4
4
IMPOSSIBLE
5

    Discussion

    Statistics


    81% Solution Ratio

    avivillaEarliest, Jul '17

    shishir_royFastest, 38188.4s

    fahim5466Lightest, 524 kB

    BruteforcekidShortest, 470B

    Submit

    Login to submit

    Editorial

    Contact with Arnab Sen Sharma Api. Read more...

    Related Contests

    SUST Intra University Programming Contest 2017 (Junior) Ended at 2017-07-26 12:30:00 +0000 UTC
    MU Tech Fest Programming Contest 2017 (Senior) Ended at 2017-11-16 09:05:00 +0000 UTC
    Replay of MU Tech Fest Programming Contest 2017 (Senior) Ended at 2017-11-20 18:00:00 +0000 UTC