Greedy Seunghyun

문제 정보

문제

Jaehyun, who teaches \(N\) children in his kindergarten, decided to give them candies, because it was his birthday! Each child is denoted as an integer number from 0 to \(N-1\). Because Jaehyun tends to give freedom to the kids, he let them take candies as much as they want. As a result, child \(i\) (\(0 \le i < N\)) took \(a_{i}\) candies.

Seunghyun, who is denoted as child \(0\), was disappointed because he couldn't obtain all the candies. After a deep thought, Seunghyun came out with an idea. He gathered all the kids in the kindergarten, and suggested to distribute candies by the following way:

  1. Seunghyun chooses an integer \(k\) which is bigger than \(0\) and smaller than \(N\).
  2. Child \(k\) must hand out one candy to each of child \(0\), child \(1\), ... child \(k-1\). After this, child \(k\) will lose \(k\) candies, and child \(0\), child \(1\), \(\cdots\), child \(k-1\) will get one candy.

All the children agreed because they thought that it was a great idea! However, as the only purpose of this suggestion was taking all the candies, Seunghyun wants to know whether he could achieve his goal by repeating this process 0 or more times.

You are to write a program which determines whether Seunghyun can get all the candies.

입력

The first line of the input contains the number of test cases \(T\).

Each test case starts with a line containing \(N\) (\(2 \le N \le 100,000\)), the number of children that Jaehyun teaches. The following line contains \(N\) space-separated integers \(a_{0}, a_{1}, \cdots, a_{N-1}\), where \(a_{i}\) (\(0 \le a_{i} \le 10^{9}\)) is the number of candies that child \(i\) has taken.

출력

For each test case, if Seunghyun can take all candies, print "POSSIBLE" (without quotes). If not print "IMPOSSIBLE" (without quotes).

예제 입력

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

예제 출력

POSSIBLE
IMPOSSIBLE
POSSIBLE

노트

1개의 댓글이 있습니다.