There is a directed graph with N vertices and N edges. The vertices are numbered 1, 2, ..., N.

The graph has the following N edges: (p_1, 1), (p_2, 2), ..., (p_N, N), and the graph is weakly connected. Here, an edge from Vertex u to Vertex v is denoted by (u, v), and a weakly connected graph is a graph which would be connected if each edge was bidirectional.

We would like to assign a value to each of the vertices in this graph so that the following conditions are satisfied. Here, a_i is the value assigned to Vertex i.

* Each a_i is a non-negative integer.
* For each edge (i, j), a_i \neq a_j holds.
* For each i and each integer x(0 ≤ x < a_i), there exists a vertex j such that the edge (i, j) exists and x = a_j holds.



Determine whether there exists such an assignment.

Constraints

* 2 ≤ N ≤ 200 000
* 1 ≤ p_i ≤ N
* p_i \neq i
* The graph is weakly connected.

Input

Input is given from Standard Input in the following format:


N
p_1 p_2 ... p_N


Output

If the assignment is possible, print `POSSIBLE`; otherwise, print `IMPOSSIBLE`.

Examples

Input

4
2 3 4 1


Output

POSSIBLE


Input

3
2 3 1


Output

IMPOSSIBLE


Input

4
2 3 1 1


Output

POSSIBLE


Input

6
4 5 6 5 6 4


Output

IMPOSSIBLE
from collections import defaultdict
import heapq as hq


def helper(n):
    q = child_L[n]
    del child_L[n]

    hq.heapify(q)
    i = 0
    while q:
        t = hq.heappop(q)
        if i < t:
            break
        else:
            i += (i == t)

    j = i + 1
    while q:
        t = hq.heappop(q)
        if j < t:
            break
        else:
            j += (j == t)

    return (i, j)


if __name__ == '__main__':

    N = int(input())
    P = list(map(lambda x: int(x) - 1, input().split()))
    # D:出している辺の本数
    D = [0] * N
    for p in P:
        D[p] += 1
    # print(D)
    child_L = defaultdict(list)
    # S:辺を出してないものリスト
    S = [p for p in range(N) if D[p] == 0]

    L = [None] * N

    while S:
        # print(child_L)
        n = S.pop()

        q = child_L[n]
        # print(q)
        del child_L[n]

        # listのqをヒープキューに変換
        hq.heapify(q)
        i = 0
        while q:
            t = hq.heappop(q)
            if i < t:
                break
            else:
                i += (i == t)

        L[n] = i
        # print(L)
        m = P[n]
        # print("m:" + str(m))
        child_L[m].append(i)
        D[m] -= 1
        if D[m] == 0:
            S.append(m)

    # print(D)
    # cycle check
    try:
        start = D.index(1)
    except ValueError:
        print('POSSIBLE')
        exit()

    s1, s2 = helper(start)
    G = []
    n = P[start]
    while n != start:
        G.append(helper(n))
        n = P[n]

    # del N, P, D, child_L, S, L

    # 可能な初期値をそれぞれシミュレート
    # 1
    n = s1
    for g in G:
        if g[0] == n:
            n = g[1]
        else:
            n = g[0]
    if n != s1:
        print('POSSIBLE')
        exit()

    # 2
    n = s2
    for g in G:
        if g[0] == n:
            n = g[1]
        else:
            n = g[0]
    if n == s1:
        print('POSSIBLE')
        exit()

    print('IMPOSSIBLE')
