Lesson 10

Programming problem. (Optional problem.) Given a permutation of integers from \(0\) to \(n\), determine its parity.

• Input format.  The first line contains the integer \(n\) (\(2 \le n \le 10^{5}\)). The next line contains \(n+1\) integers separated by spaces — the elements of the permutation. It is guaranteed that the line defines a valid permutation, that is, \(\pi[i] \ne \pi[j]\) for \(i \ne j\) and \(0 \le \pi[i] \le n\).


• Output format.  Output one number: \(0\) if the permutation is even, and \(1\) if it is odd.

In this problem, the number of elements is already large enough so a quadratic time algorithm will not fit into the time limit.

3
3 0 2 1

0