Charles Darwin has made it to the Galapagos Islands, and is observing turtles - more specifically, there are $$$n$$$ ($$$1 \leq n \leq 200,000$$$) turtles with their nests (these turtles have nests) lined up in a row. They all lay an integer number of eggs; the $$$i$$$'th turtle's nest has $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$) eggs. He also observes diversity in that no 2 turtles lay the same number of eggs. Darwin likes things to be ordered and is therefore displeased that the nests are not sorted in increasing order. He is allowed to do the following operation - he can choose $$$a_i, a_{i+1}, a_{i+2}$$$ and reorder them to be $$$a_{i+2}, a_i, a_{i+1}$$$ in place. Determine whether it is possible for Darwin to obtain a sorted row of nests (in increasing order) by doing this operation any number of times.
The first line will contain an integer $$$n$$$. The next line contains $$$n$$$ space separated integers $$$a_1, a_2 \cdots a_n$$$.
Output a single bit - $$$1$$$ if it is possible for Darwin to sort the nests, and $$$0$$$ if it is not.
33 1 2
1
41 2 4 3
0