C. Christopher Robin is Learning Sorting Permutations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

// WRITTEN BY ME AND MR CORMEN HELPD
int psort(int L, int R) {
    if (L >= R)
        return 0;
    
    int i = L;
    int j = R;
    int x = Random.next();
    int x0 = A[x];
    
    assert(L <= x && x <= R);
    
    while (i < j) {
        while (A[i] < A[x]) i++;
        while (A[j] > A[x]) j–;
        if (i <= j) {
            if (i == x) 
                x = j;
            else if (j == x)
                x = i;
            swap(A[i], A[j]);
            i++;
            j–;
        }
    }

    swap(A[x], A[x0]);
    
    return R - L + psort(L, x0 - 1) + psort(x0 + 1, R);
}

In the last line, function calls are made from left to right: psort(L, x0 - 1) is called first, psort(x0 + 1, R) is called second.

Given $$$n$$$ and the sequence returned by Random.next(), find an array A such that psort(1, n) will return the maximal possible value. Array A should be a permutation of $$$n$$$ integers from $$$1$$$ to $$$n$$$. Please note that sorting may fail due to assertion statement.

Input

There is a single integer $$$n$$$ on the first line ($$$1 \le n \le 50$$$). The second line contains $$$n$$$ integers ranging from $$$1$$$ to $$$n$$$ separated by spaces. These are the numbers returned by $$$n$$$ successive calls of Random.next() in the order they were made.

Output

If there is no such array A, output "No solution". Otherwise, output "Solution exists" on the first line and the array A itself on the second line. If there are several possible arrays such that psort(1, n) returns the maximal possible value, output any one of them.

Examples
Input
3
1 2 3
Output
Solution exists
1 2 3
Input
7
1 7 1 7 1 7 1
Output
No solution