Recovering the Seed

Professor Pang used a xor‐shift random generator to shuffle the team numbers from 1 to n. His program works as follows. Let x be a 64‐bit unsigned integer seed. The function rand() is defined as

\[ x \mathrel{{\oplus}=} (x \ll 13), \quad x \mathrel{{\oplus}=} (x \gg 7), \quad x \mathrel{{\oplus}=} (x \ll 17), \quad \text{and then } rand() = x. \]

The program then initializes an array a with a[i] = i for i from 1 to n, and for each i it performs the swap

[ a[i] \leftrightarrow a[ (rand() \bmod i) + 1 ]. ]

After the shuffle the program prints the resulting permutation. One day Professor Pang forgot the seed x he used. Given the printed permutation and n, your task is to recover the original seed x.

Note: It is guaranteed that the printed permutation was produced by the algorithm above for some nonnegative integer seed x (with 64‐bit unsigned arithmetic). The xor–shift generator is invertible and the procedure uniquely determines the seed.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10). The second line contains n space-separated distinct integers a₁, a₂, …, a_n representing the permutation printed by the program.

outputFormat

Output the original seed x (an unsigned 64‐bit integer) that Professor Pang entered.

sample

3
3 1 2

0