Even or Odd

Time Limit : 5 seconds Memory Limit : 10MB

We define f(p1,p2,…,pn) as the number of inversion pairs(an inversion pair is such a pair (pi, pj) which i < j and pi > pj). Here p1p2p3…pn is a permutation of 123..n, i.e. {p1,p2,p3,…,pn} = {1,2,…, n}.

We call permutation p1p2p3…pn an even permutation if f(p1,p2,…,pn) is even. As you can guess, the other permutations are called odd permutations.

Maybe you can easily calculate the function f, but we are only interested in the value (-1) f(p1,p2,…,pn).For this purpose, we want to know whether a permutation is even.

For example f(1,2,3,4) = 0, so 1234 is a even permutation; f(2,4,1,3) = 3, thus 2413 is an odd permutation.

Input:

The input contains several cases.

Each case has two lines, an integer N (1<=N<=2000000) on the first line and the permutation on the second line(numbers are separated with a blank). Input ends with an zero in a single line.

Output:

For each case, output one line. Output “EVEN” if the permutation is an even permutation, otherwise output “ODD”.

Sample Input:

2
1 2
4
2 4 1 3
0

Sample Output:

EVEN
ODD

Hint:

Huge input, cin(c++) and Scanner(Java) will TLE!

• Re:shu problem d (1276) dabiaoyanjun 2006-10-21 14:29:43