Sort Books by Inversion Parity

You are given a sequence of n integers representing the order of books. The task is to decide whether it is possible to sort the books in ascending order using only operations that preserve the parity of the number of inversions. In other words, you must determine if the total number of inversions in the given sequence is even. If the number of inversions is even, output YES; otherwise, output NO. The inversion count is defined as the number of pairs (i, j) such that i < j and books[i] > books[j].

The solution involves counting the inversions and checking whether this count is even. This property is critical as only even permutations can be sorted by a series of adjacent swaps under certain constraints. Your program should read input from stdin and write the answer to stdout.

inputFormat

The input consists of two lines:

• The first line contains a single integer n (1 ≤ n ≤ 10⁵), representing the number of books.
• The second line contains n space-separated integers which denote the current order of the books.

outputFormat

Output a single line containing either YES if it is possible to sort the books into ascending order (i.e. if the inversion count is even) or NO otherwise.

3
3 1 2

YES