n,*l=list(map(int,open(0)));e=enumerate

d={j:i for i,j in e(sorted(l))}

print((sum([(d[j]+i)%2for i,j in e(l)])//2))
n,*a=list(map(int,open(0)))

print((len(set(a[::2])^set(sorted(a)[::2]))//2))
n, *l = list(map(int, open(0)))
e = enumerate
d = {j: i for i, j in e(sorted(l))}
print((sum([(d[j] + i) % 2 for i, j in e(l)]) // 2))

n, *a = list(map(int, open(0)))
print((len(set(a[::2]) ^ set(sorted(a)[::2])) // 2))

-n, *l = list(map(int, open(0))) -e = enumerate -d = {j: i for i, j in e(sorted(l))} -print((sum([(d[j] + i) % 2 for i, j in e(l)]) // 2)) +n, *a = list(map(int, open(0))) +print((len(set(a[::2]) ^ set(sorted(a)[::2])) // 2))