A conveyor holds n crates whose labels are a permutation of 1..n. The only allowed operation is swapping two crates that are currently adjacent. The number of adjacent swaps needed to sort the crates into 1, 2, ..., n can vary, but its parity (even or odd) is fixed and equals the parity of the number of out-of-order pairs.
Report EVEN if the crates can be sorted using an even number of adjacent swaps, or ODD otherwise. The input is guaranteed to be a permutation of 1..n.
Line 1: an integer n, the number of crates.
Line 2: n space-separated integers, a permutation of 1..n.
A single line: EVEN or ODD.
Example 1
Input
4 2 1 4 3
Expected
EVEN
Explanation
The out-of-order pairs are (2,1) and (4,3): two of them, an even count, so EVEN.
Example 2
Input
3 3 2 1
Expected
ODD
Explanation
The out-of-order pairs are (3,2), (3,1) and (2,1): three of them, an odd count, so ODD.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →