Problem:
 Score : 600 points    Problem Statement Snuke got an integer sequence of length N from his mother, as a birthday present. The i -th (1 ≦ i ≦ N) element of the sequence is a_i . The elements are pairwise distinct.
He is sorting this sequence in increasing order.
With supernatural power, he can perform the following two operations on the sequence in any order:   Operation 1 : choose 2 consecutive elements, then reverse the order of those elements.  Operation 2 : choose 3 consecutive elements, then reverse the order of those elements.   Snuke likes Operation 2 , but not Operation 1 . Find the minimum number of Operation 1 that he has to perform in order to sort the sequence in increasing order.      Constraints  1 ≦ N ≦ 10^5  0 ≦ A_i ≦ 10^9  If i ≠ j , then A_i ≠ A_j .  All input values are integers.         Input The input is given from Standard Input in the following format:  N  A_1 : A_N       Output Print the minimum number of times Operation 1 that Snuke has to perform.        Sample Input 1 4
2
4
3
1      Sample Output 1 1  The given sequence can be sorted as follows:   First, reverse the order of the last three elements. The sequence is now: 2,1,3,4 .  Then, reverse the order of the first two elements. The sequence is now: 1,2,3,4 .   In this sequence of operations, Operation 1 is performed once. It is not possible to sort the sequence with less number of Operation 1 , thus the answer is 1 .       Sample Input 2 5
10
8
5
3
2      Sample Output 2 0

Solution (Python):
from copy import deepcopy
N = int(input())
A = [int(input()) for i in range(N)]

B = deepcopy(A)
B.sort()
odd, even = set(), set()
for i in range(N):
    if i % 2 == 0:
        even.add(B[i])
    else:
        odd.add(B[i])

ans = 0
for i in range(N):
    if i % 2 == 0 and A[i] not in even:
        ans += 1
    if i % 2 == 1 and A[i] not in odd:
        ans += 1

print(ans // 2)

Solution (Python):
n = int(input())
nums = [[int(input()), i] for i in range(n)]
nums.sort()
ans = 0

for i in range(n):
    if abs (i - nums[i][1]) % 2 == 1:
        ans += 1

print(ans // 2)

Solution (Python):

import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


N = int(input())
A = []
for i in range(N):
    A.append(int(input()))


B = sorted(A)
d = {}


for i in range(N):
    d[A[i]] = i % 2

count = 0
for i in range(N):
    
    count += (d[B[i]] + i) % 2


print(count//2)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]

sortedA = sorted(A)
dic = {}
for i in range(N):
    dic[sortedA[i]] = i

ans = 0
for i in range(N):
    if i % 2 != dic[A[i]] % 2:
        ans += 1
print(ans//2)

Solution (Python):
n = int(input())
nums = []
evens = set()
for i in range(n):
  tmp = int(input())
  nums.append(tmp)
  if i%2==0:
    evens.add(tmp)
nums.sort()
count = 0
for j in range(n):
  if j%2 == 0:
    if nums[j] not in evens:
      count += 1
print(count)

Solution (Python):
N=int(input())
A=[]
for i in range(N):
  a=int(input())
  A.append(a)
res=sorted(A)

def binary_search(x):
  l=0
  r=N-1

  while True:
    mid=(l+r)//2
    if res[mid]==x:
      return mid
    elif res[mid]>x:
      r=mid-1
    elif res[mid]<x:
      l=mid+1

ans=0
for j,k in enumerate(A):
  cnt=binary_search(k)
  if abs(j-cnt)%2==1:
    ans+=1

print(ans//2)

Solution (Python):


n = input()
elems = []
for _ in range(n):
    elems.append(input())

inds = range(n)
inds.sort(key=lambda x: elems[x])

resp = 0
for i in range(n):
    if (inds[i] + i) % 2:
        resp += 1

print(resp / 2)

Solution (Python):
def minimumOpt1(seq):
    dest = {}
    b = sorted(seq)
    for i in xrange(len(b)):
        dest[b[i]] = i
    foo = 0
    for i in xrange(0, len(seq), 2):
        if dest[seq[i]]%2==1:
            foo += 1
    return foo

def main():
    n = int(raw_input().strip())
    seq = [0] * n
    for i in xrange(n):
        seq[i] = int(raw_input().strip())
    print minimumOpt1(seq)

if __name__ == '__main__':
    main()

Solution (Python):
def minimumOpt1(seq):
    dest = {}
    b = sorted(seq)
    for i in xrange(len(b)):
        dest[b[i]] = i
    foo = 0
    for i in xrange(0, len(seq), 2):
        if dest[seq[i]]%2==1:
            foo += 1
    return foo

def main():
    n = int(raw_input().strip())
    seq = []
    for i in xrange(n):
        seq.append(int(raw_input().strip()))
    print minimumOpt1(seq)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import math
N = int(input())
s = [int(input()) for _ in range(N)]
sn=np.array(s)
sa=sn.argsort()
x=0
for i in range(N):
  if i %2 != sa[i] %2:
    x+=1
print(math.ceil(x/2))

Solution (Python):
N = int(input())
src = [(int(input()), i) for i in range(N)]
src.sort()

odd = 0
for new_order, (a, old_order) in enumerate(src):
    if (new_order - old_order) % 2:
        odd += 1
print(odd // 2)

Solution (Python):
n = int(input())
ls = []
for i in xrange(0, n):
    ls.append(int(input()))
sls = sorted(ls)
st = {j for i, j in enumerate(ls) if i % 2 == 1}
sst = {j for i, j in enumerate(sls) if i % 2 == 1}
print(len(st.difference(sst)))

Solution (Python):
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque








def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)


def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))





def main():
	N=I()
	A=ALL_IL()
	B=sorted(A.copy())

	a = set([A[i] for i in range(0,N,2)])
	b = set([B[i] for i in range(0,N,2)])

	print(len(a-b))


if __name__ == '__main__':
	main()

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N = int(input())
    A_list = list(sorted([(int(input()), i) for i in range(N)]))
    a_list = [i for a, i in A_list]
    ans = 0
    for i, a in enumerate(a_list):
        ans += (i % 2 != a % 2)
    print(ceil(ans, 2))


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin

def binarysearch(cadena,x):
	low,hi = 0,len(cadena)
	while low+1 != hi:
		mid = low +((hi - low)//2)
		if x < cadena[mid]:
			hi = mid
		else:
			low = mid
	return low

def main():
	N = int(stdin.readline().strip())
	i,number,copy = 0,[-1 for x in range(N)],[-1 for x in range(N)]
	while i < N:
		x = int(stdin.readline().strip())
		number[i] = x
		copy[i] = x
		i+=1
	i,op1 = 0,0
	copy.sort()
	while i < N:
		pos = binarysearch(copy,number[i])
		if (abs(pos-i))%2!= 0:
			op1+=1
		i+=1
	ans = op1//2
	print(ans)
main()

Solution (Python):
n = int(raw_input())
ls = [int(raw_input()) for _ in range(n)]
sls = sorted(ls)
st = {j for i,j in enumerate(ls) if i % 2 == 1}
sst = {j for i,j in enumerate(sls) if i % 2 == 1}
print len(st.difference(sst))

Solution (Python):
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')


def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())


def join(s):
    return ''.join(s)


def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)


def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m


def index(a, x):
    
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1


def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m



n=i()
a=[]
for j in range(n):
    a.append((i(),j))
a.sort()
cnt=0
for j in range(n):
    if a[j][1]%2!=j%2:
        cnt+=1


print cnt/2

Solution (Python):
import sys



N = int(raw_input())
seq = []
for x in range(N):
	a = long(raw_input())
	seq.append((a, x))
seq.sort()

count = 0
for x in range(N):
	a, i = seq[x][0], seq[x][1]
	if ((x - i) % 2):
		count += 1

print str(count / 2)

Solution (Python):
import numpy as np

N = int(raw_input())
A = [0] * N
for idx in xrange(N):
  A[idx] = int(raw_input())
A = np.array(zip(A,range(N)))
B = np.array(sorted(A, key=lambda x:x[0]))
C = np.array([x[1] for x in B])
D = np.array(range(N))
C = C % 2
D = D % 2
E = np.abs(C - D)

print sum(E)/2

Solution (Python):
def solve(a):
	l = len(a)
	h = l//2 + l%2
	a0 = [a[2*i] for i in range(h)]
	b = a.copy()
	b.sort()
	b0 = [b[2*i] for i in range(h)]

	a0 = set(a0)
	b0 = set(b0)

	return len(a0 - b0)
n = int(input())
a = [int(input()) for i in range(n)]
print(solve(a))

Solution (Python):

n = int(input())
a = [[int(input()), i] for i in range(n)]
a.sort()

ans = 0

for i in range(0, n, 2):
    if a[i][1] % 2 == 1:
        ans += 1

print(ans)

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]

even_num = set((a[i] for i in range(0,n) if i % 2 == 0))

a.sort()

odd_num = set((a[i] for i in range(0, n) if i % 2 == 1))

count = len(even_num & odd_num)
print(count)

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]

even_num = set([a[i] for i in range(0,n) if i % 2 == 0])

a.sort()

odd_num = set([a[i] for i in range(0, n) if i % 2 == 1])

count = len(even_num & odd_num)
print(count)

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]

even_num = set([a[i] for i in range(0,n) if i % 2 == 0])

a = sorted(a)

odd_num = set([a[i] for i in range(0, n) if i % 2 == 1])

count = len(even_num & odd_num)
print(count)

Solution (Python):
N = input()
a = sorted([(int(raw_input()), i) for i in xrange(N)])
print sum([i%2 != j[1]%2 for i, j in enumerate(a)]) / 2

Solution (Python):
n=int(input())
arr=[]
dic={}
for i in range(0,n):
    a = int(input())
    arr.append(a)
    dic[a]=i%2

brr=sorted(arr)
diff=0
for i in range(0,n):
    if dic[brr[i]] != i%2:
        diff+=1
print(diff//2)

Solution (Python):
def solve():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    e = [a[i] for i in range(0, n, 2)]
    a.sort()
    o = set(a[i] for i in range(1, n, 2))
    ans = 0
    for i in range((n + 1) // 2):
        if e[i] in o:
            ans += 1
    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Solution (Python):

import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N = int(raw_input())
A = [int(raw_input()) for i in xrange(N)]

B = sorted(A)
X = set([A[i] for i in xrange(N) if i%2 == 0])
Y = set([B[i] for i in xrange(N) if i%2 == 0])

print len(Y - X)

Solution (Python):
from sys import stdin

n=int(input())
valeurs=[0]*n
minimum=0
for i in range(n):
    valeur=int(stdin.readline())
    valeurs[i]=[valeur,i]
valeurs.sort()
compteur=[0]*2
for i in range(n):
    indice=valeurs[i][1]
    if i%2!=indice%2:
        compteur[indice%2]+=1
print(max(compteur))

Solution (Python):
n = input()
A = [int(raw_input()) for i in xrange(n)]
B = A[0:n:2]
C = A[1:n:2]
A.sort()
B.sort()
C.sort()
ans = 0
idxB = 0
idxC = 0
for i in xrange(n):
    if i%2:
        if idxB < len(B) and B[idxB] == A[i]:
            ans += 1
    else:
        if idxC < len(C) and C[idxC] == A[i]:
            ans += 1
    if idxB < len(B) and B[idxB] == A[i]:
        idxB += 1
    if idxC < len(C) and C[idxC] == A[i]:
        idxC += 1
print ans/2

Solution (Python):
n = input()
a = []
b = []
l = []
for _ in xrange(n):
    t = input()
    if _%2 == 0:
        a.append(t)
    else:
        b.append(t)
    l.append(t)
a = sorted(a)
b = sorted(b)
l = sorted(l)
c = 0
i = 0
for k,m in enumerate(l):
    if i < len(a) and m == a[i]:
        i += 1
        if k%2 == 1:
            c += 1
    else:
        if k%2 == 0:
            c += 1
print c/2

Solution (Python):
from sys import stdin
n = int(stdin.readline())
a = [int(stdin.readline()) for _ in xrange(n)]
b = [a[0::2], a[1::2]]
ans = t = 0
a.sort()
d = dict()
for x in a:
    d[x] = t
    t = 1 - t
for i, l in enumerate(b):
    for x in l:
        ans += d[x] ^ i
print ans / 2

Solution (Python):
N = int(input())
a = [int(input())  for i in range(N)]
index = sorted(range(len(a)), key=lambda k: a[k])
count = 0
for i in range(N):
    if (index[i]+i)%2 ==1:
        count = count + 1
print('%s' % str(count//2))

Solution (Python):
n = input()
l1 = []

for i in range(n):
	t = input()
	l1.append(t)

l2 = sorted(l1)

s1, s2 = set([]), set([])

for i in range(n):
	if i % 2 == 1:
		s1.add(l1[i])
		s2.add(l2[i])

print len(s1) - len(s1.intersection(s2))

Solution (Python):
N = int(input())
xs = list(map(int, (input() for _ in range(N))))
ss = sorted(xs)
odd1 = set((x for i, x in enumerate(xs) if i % 2 == 1))
even2 = set((s for i, s in enumerate(ss) if i % 2 == 0))
print(len(odd1 & even2))

Solution (Python):



N = int(input())
nums = [0] * N
for pos in range(N):
    nums[pos] = int(input())
snums = sorted(nums[:])
rank = {}
for i,e in enumerate(snums):
    rank[e] = i+1

rev = 0
for i,e in enumerate(nums):
    if (i + rank[e]) % 2 == 0:
        rev += 1
print(rev // 2)

Solution (Python):
n = int(raw_input())
values = [ int(raw_input()) for i in range(n) ]
place = { x: i for i, x in enumerate(sorted(values)) }
count = 0
for i, x in enumerate(values):
    if i % 2 != place[x] % 2:
        count += 1
result = count // 2 + count % 2
print(result)

Solution (Python):
n = int(input())
A = [0]*n

for i in range(n):
	A[i] = int(input())

SO = A[:]
SO.sort()


def check(mid, now):
	return now >= SO[mid]


def binarySearch(small, big, now):
	mid = (big + small) // 2
	if big == small or big == small + 1:
		if SO[big] == now:
			return big
		else:
			return small
	else:
		if check(mid, now):
			return binarySearch(mid, big, now)
		else:
			return binarySearch(small, mid, now)



ans = 0
for i in range(n):
	now = A[i]
	gi = binarySearch(0, n-1, now)
	if i % 2 != gi % 2:
		ans += 1


print(ans // 2)

Solution (Python):
import bisect
n=int(raw_input())
a=[int(raw_input()) for _ in xrange(n)]
cnt=0
sa=sorted(a)
for i in xrange(n):
    if abs(i-bisect.bisect_left(sa,a[i]))%2!=0:
        cnt+=1
print(cnt/2)

Solution (Python):
import operator

N = int(raw_input())

A = [int(raw_input())-1 for i in range(N)]

Dindices = [i for (i,a) in sorted(enumerate(A), key=operator.itemgetter(1))]

print sum(1 for (i,Di) in enumerate(Dindices) if (Di-i)%2 == 1) // 2

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]
sorted_A = sorted(A)
d = {}
for i in range(N):
    d[sorted_A[i]] = i

cnt = 0
for i in range(N):
    if i % 2 == 0 and d[A[i]] % 2 != 0:
        cnt += 1
    elif i % 2 != 0 and d[A[i]] % 2 == 0:
        cnt += 1
ans = cnt // 2
print(ans)

Solution (Python):

import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9


def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

N = n()


pos = {}

A = []
for i in xrange(N):
    a = n()
    A.append(a)
    pos[a] = i

A.sort()

c = 0
ok = True
for i in xrange(N):
    if pos[A[i]] % 2 != i % 2:
        c += 1

print c / 2

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**9

n = int(input())
a = [[int(input()),_] for _ in range(n)]
a.sort()
r = 0
for i in range(0,n,2):
    if a[i][1] % 2 == 1:
        r += 1
print(r)

Solution (Python):
N=int(input())
A=[(int(input()),i) for i in range(N)]
A.sort()
Ans=0
for i in range(0,N,2):
    if A[i][1] % 2 == 1:
        Ans += 1
print(Ans)