G. Galapagos
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

The first line will contain an integer $$$n$$$. The next line contains $$$n$$$ space separated integers $$$a_1, a_2 \cdots a_n$$$.

Output

Output a single bit - $$$1$$$ if it is possible for Darwin to sort the nests, and $$$0$$$ if it is not.

Examples
Input
3
3 1 2
Output
1
Input
4
1 2 4 3
Output
0