n = int(eval(input()))

a = [int(eval(input())) for _ in range(n)]

b = sorted(a)



c = dict()

for i in range(n):

    c[b[i]] = i&1



d = 0

for i in range(n):

    d += c[a[i]]^i&1



print((d>>1))
n, *a = list(map(int, open(0).read().split()))



b = []

for i in range(n):

    b.append((a[i], i))

b.sort()



ans = 0

for i in range(n):

    if b[i][1] % 2 != i % 2:

        ans += 1

print((ans // 2))

n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]
b = sorted(a)
c = dict()
for i in range(n):
    c[b[i]] = i & 1
d = 0
for i in range(n):
    d += c[a[i]] ^ i & 1
print((d >> 1))

n, *a = list(map(int, open(0).read().split()))
b = []
for i in range(n):
    b.append((a[i], i))
b.sort()
ans = 0
for i in range(n):
    if b[i][1] % 2 != i % 2:
        ans += 1
print((ans // 2))

-n = int(eval(input())) -a = [int(eval(input())) for _ in range(n)] -b = sorted(a) -c = dict() +n, *a = list(map(int, open(0).read().split())) +b = [] -    c[b[i]] = i & 1 -d = 0 +    b.append((a[i], i)) +b.sort() +ans = 0 -    d += c[a[i]] ^ i & 1 -print((d >> 1)) +    if b[i][1] % 2 != i % 2: +        ans += 1 +print((ans // 2))