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):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N = getN()
A = getArray(N)
s = sorted(A)
alta = {}
for i in range(N):
    alta[s[i]] = i
A = [alta[i] for i in A]

"""
N <= 100000
O(NlogN)まで
1つとばし交換をたくさん行う
隣接とばしの最小回数は
N = 4
A = [2, 4, 3, 1]の場合最終形は
A = [1, 2, 3, 4]
バブルソートの交換回数
1, 2, 3の自分より左にある自分より大きいものの数

1, 3, 5...番目にあるものは1, 3, 5...番目にしかいけない
いくつ路線を変える必要があるか
"""

def counter(array):
    n = len(array)
    cnt = 0
    for i in range(n):
        if (array[i] % 2) ^ (i % 2):
            cnt += 1
    return cnt

print(counter(A) // 2)

Solution (Python):
n = int(input())
nums = [int(input()) for _ in range(n)]

sorted_nums = sorted(nums)

nums_idx = {}
for idx, num in enumerate(nums):
    nums_idx[num] = idx

sorted_nums_idx = {}
for idx, num in enumerate(sorted_nums):
    sorted_nums_idx[num] = idx

ans = 0
for num in sorted_nums:
    if (nums_idx[num] - sorted_nums_idx[num]) % 2 :
        ans += 1

print(ans // 2)

Solution (Python):
n=int(input())
a=[]
d={}
e={}
f=1
for i in range(n):
  inp=int(input())
  a.append(inp)
  if not inp in d:
    d[inp]=0
    e[inp]=0
  if f:
    d[inp]+=1
  f=1-f
a.sort()
f=1
for i in a:
  if f:
    e[i]+=1
  f=1-f
c=0
for i in d:
  c+=abs(d[i]-e[i])
print(c//2)

Solution (Python):
from bisect import bisect_left
N = int(input())
A = [0]*N
B = [0]*((N+1)//2)
for i in range(N):
    a = int(input())
    A[i] = a
    if i % 2 == 0:
        B[i//2] = a
A.sort()

ct = 0
for i in range((N+1)//2):
    if bisect_left(A, B[i]) % 2 == 1:
        ct += 1
print(ct)

Solution (Python):
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    S = A.copy()
    S.sort()
    from_index = {a: i for i, a in enumerate(A)}
    to_index = {s: i for i, s in enumerate(S)}
    cnt = 0  
    for a in A:
        if abs(from_index[a] - to_index[a]) % 2 == 1:
            cnt += 1
    print(cnt // 2)


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ai = [(a, i) for i, a in enumerate(A)]
    ai.sort()
    ans = 0
    for i, (a, j) in enumerate(ai):
        if i % 2 != j % 2:
            ans += 1
    return ans // 2


def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
from collections import defaultdict
d1=defaultdict(int)
d2=defaultdict(int)
ar=[]
for i in range(n):
    k=int(input())
    d1[k]=i
    ar.append(k)
ar.sort()
for i in range(n):
    k=ar[i]
    d2[k]=i
c=0
for i in ar:
    a,b=d1[i],d2[i]
    if (a+b)%2==1:
        c+=1
print(c//2)

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

p.sort()
cou = 0
for k in range(n):
    cou += (p[k][1] - k) % 2

print(-(-cou//2))

Solution (Python):
n = int(input())
a = [int(input()) for _ in range(n)]
a_sorted = sorted(a)
a_sorted_pos = {}
for i in range(n):
    a_sorted_pos[a_sorted[i]] = i
ans = 0
for i in range(0, n, 2):
    if (i + a_sorted_pos[a[i]]) % 2 == 1:
        ans += 1
print(ans)

Solution (Python):
n=int(input())
a=[int(input()) for _ in range(n)]
print(len(set(a[::2])^set(sorted(a)[::2]))//2)

Solution (Python):
from bisect import bisect_left


N, *A = map(int, open(0).read().split())
sorted_A = sorted(A)
ans = 0
for i in range(N):
    idx = bisect_left(sorted_A, A[i])
    if i % 2 != idx % 2:
        ans += 1
print(ans // 2)

Solution (Python):
N = int(input())

A = [[int(input()),i] for i in range(N)]

Asort = sorted(A)

ans = 0
for key,val in enumerate(Asort):
    if abs(key-val[1])%2==1:
        ans += 1
print(ans//2)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
A = [(A[i],i) for i in range(N)]
A = sorted(A,key=lambda x:x[0])
cnt = 0
for i in range(N):
    a,j = A[i]
    if (i-j)%2==1:
        cnt += 1
print(cnt//2)

Solution (Python):
n, *a = 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)

Solution (Python):
n=int(input())
a=[int(input()) for i in range(n)]
b=list(sorted(a))
dict={}
for i in range(n):
  dict.setdefault(b[i],i)
cnt=0

for i,v in enumerate(a):
  if abs(dict[v]-i)%2==1:
    cnt+=1
    

print(cnt//2)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
a=[int(input()) for i in range(n)]
b=sorted(a)
dic={}
for i,x in enumerate(b):
	dic[x]=i
for i in range(n):
	a[i]=dic[a[i]]
cnt=0
for i in range(n):
	if i%2!=a[i]%2:
		cnt+=1
print(cnt//2)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    A = list(in_all())

    sort_ind = sorted(range(N), key=lambda i: A[i])

    cnt = 0
    for i in range(N):
        cnt += abs(i - sort_ind[i]) & 1

    print(cnt // 2)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=[int(input()) for _ in range(n)]
d={}
for i,x in enumerate(sorted(a)):
  d[x]=i%2
cnt=0
for i,x in enumerate(a):
  if d[x]!=i%2:cnt+=1
print(cnt//2)

Solution (Python):
from bisect import bisect_left
N = int(input())
A = list(int(input()) for _ in range(N))
S = sorted(A)
A = [bisect_left(S,a) for a in A]
print((sum((i-j)%2 for i,j in enumerate(A))+1)//2)

Solution (Python):
from math import ceil
N = int(input())
A = []
for i in range(N):
    A.append((i, int(input())))
A.sort(key=lambda x:x[1])
B = [0]*N
for i, p in enumerate(A):
    j, _ = p
    B[j] = i
res = 0
for i, b in enumerate(B):
    if (i-b)%2:
        res += 1
print(ceil(res/2))

Solution (Python):
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = [[int(input()), i] for i in range(n)]
    a.sort()
    
    ans = 0
    for i in range(n):
        if i%2 != a[i][1]%2:
            ans += 1
    
    print(ans//2)


if __name__ == "__main__":
    main()

Solution (Python):
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = [int(input()) for i in range(n)]
AS=sorted(A)
C = collections.Counter()
for i,ai in enumerate(AS):
  C[ai] = i
odd = 0
even = 0
for i,ai in enumerate(A):
  if C[ai] % 2 != i % 2:
    
    if i % 2 == 0:
      odd += 1
    else:
      even += 1
m = min(odd,even)
odd -= m
even -= m
count += m
count += max(odd,even)

print(count)

Solution (Python):
import sys
import math
import collections
import bisect
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    n = ni()
    a = [ni() for _ in range(n)]
    a_sorted = sorted(a)

    ans = 0
    for i, ai in enumerate(a):
        idx = bisect.bisect_left(a_sorted, ai)
        if (idx - i) % 2:
            ans += 1

    print(ans // 2)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
l=[int(input()) for _ in range(n)]
a=set(l[::2])
b=set(sorted(l)[::2])
print(len(b-a))

Solution (Python):
n=int(input())
l=[int(input()) for _ in range(n)]
a=set(l[::2])
l.sort()
b=set(l[::2])
print(len(b-a))

Solution (Python):



n = int(input())
l = [int(input()) for _ in range(n)]
ll = set(l[::2])
l.sort()
llr = set(l[::2])
print(len(ll - llr))

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

A.sort()
AO.sort()

SAO = set(AO)

cnt = 0
for a in A[0::2]:
  if a not in SAO:
    cnt += 1
    
print(cnt)

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	n=II()
	A=[II() for _ in range(n)]
	s=set()
	for i,v in enumerate(A):
		if i%2:
			s.add(v)
	A.sort()
	ss=set()
	for i,v in enumerate(A):
		if i%2:
			ss.add(v)
	ans=len(s)

	sss=s&ss

	print(ans-len(sss))
















if __name__ == "__main__":
	main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N = INT()
A = [INT() for _ in range(N)]

zipped = {x:i+1 for i, x in enumerate(sorted(A))}
A = [zipped[x] for x in A]

print(sum(x%2==0 for x in A[::2]))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N = INT()
A = [[INT(), i] for i in range(N)]

A.sort(key = lambda x:x[0])

cnt = 0
for i, (x, idx) in enumerate(A):
	if i%2 != idx%2:
		cnt += 1

print(cnt//2)

Solution (Python):
n=int(input())
A=[]
for i in range(n):
    A.append(int(input()))

B=sorted(A[::2])
C=sorted(A)
dic={}
for i in range(n):
    dic[C[i]]=i

ans=0
for i in range(len(B)):
    if dic[B[i]]%2==1:
        ans+=1
print(ans)

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = [int(input()) for _ in range(n)]
    A_S = sorted(A)
    IDX = defaultdict(int)
    for idx, a in enumerate(A_S):
        IDX[a] = idx + 1

    res = 0
    for i in range(n):
        if IDX[A[i]] % 2 != (i + 1) % 2:
            res += 1
    print(res // 2)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = []
for i in range(n):
    lst1.append([int(readline()),i])

lst2 = sorted(lst1)
eo = [0]*2

for i,(j,k) in enumerate(lst2):
    if even(i):
        if not even(k):
            eo[0] += 1
    else:
        if even(k):
            eo[1] += 1



print(min(eo[0],eo[1])+abs(eo[1]-eo[0]))

Solution (Python):
n = int(input())
a = []
for i in range(n):
	a.append(int(input()))
s1, s2 = set(), set()
for i in range(0, n, 2):
	s1.add(a[i])
a.sort()
for i in range(0, n, 2):
	s2.add(a[i])
print(len(s1 ^ s2) // 2)

Solution (Python):
n,*a=map(int,open(0))
print(len({*a[::2]}^{*sorted(a)[::2]})//2)

Solution (Python):
n,*a=map(int,open(0))
print(len({*a[::2]}^{*sorted(a)[::2]})//2)

Solution (Python):
from collections import Counter
n=int(input())
a=[int(input()) for i in range(n)]
b=Counter(a[::2])
a.sort()
c=Counter(a[::2])

ans=0
for i in b:
	if i in c:
		ans+=abs(b[i]-c[i])
	else:
		ans+=b[i]
print(ans)

Solution (Python):
n=int(input())
a =[int(input()) for i in range(n)]
res = [[a[i],i]for i in range(n)]
res.sort()
ret =0
for i in range(n):
    if res[i][1]%2 != i%2:ret+=1
print(ret//2)

Solution (Python):
n = int(input())
alst = [int(input()) for _ in range(n)]
blst = alst.copy()
blst.sort()
cnt = 0
dic = {}
for i, num in enumerate(blst):
    dic[num] = i % 2
for i, num in enumerate(alst):
    if dic[num] != i % 2:
        cnt += 1
print(cnt // 2)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = [[int(readline()), i] for i in range(1, n + 1)]
    a.sort()

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


if __name__ == '__main__':
    main()

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

odd_n = set()
even_n = set()

for i in range(N):
    if(i%2 == 0):
        even_n.add(a[i])
    else:
        odd_n.add(a[i])
    
cnt= 0    
    
for i in range(N):
    if(i%2 == 0):
        if(A[i] not in even_n):
            cnt += 1
    else:
        if(A[i] not in odd_n):
            cnt += 1
print(cnt//2)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=[int(input()) for i in range(n)]
ki,gu={},{}
for i in range(n):
    if i%2==0:
        ki[a[i]]=1
    else:
        gu[a[i]]=1

so=sorted(a)


ans=0
for i in range(n):
    if i%2==0:
        if so[i] in ki:
            pass
        else:
            ans+=1
    else:
        if so[i] in gu:
            pass
        else:
            ans+=1
print(ans//2)

Solution (Python):
n = int(input())
A = [int(input()) for _ in range(n)]
d = {element: i for i, element in enumerate(sorted(set(A)))}
ans = 0
for i in range(n):
    if i % 2 != d[A[i]] % 2:
        ans += 1
print(ans // 2)

Solution (Python):
n=int(input())
a=[int(input()) for _ in range(n)]
aa=a.copy()
aa.sort()
import bisect
a=[bisect.bisect_left(aa,x) for x in a]
ans=0
for i in range(n):
  if (i-a[i])%2==0:
    pass
  else:
    ans+=1
print(ans//2)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = [INT() for _ in range(N)]
zipped = {x:i+1 for i, x in enumerate(sorted(set(A)))}
A = [zipped[x] for x in A]

print(sum(x%2==0 for x in A[::2]))

Solution (Python):
N=int(input())
A=[int(input()) for i in range(N)]
P=0
B=sorted(list(set(A)))
C=0
E=dict()
for i in range(N):
  E[B[i]]=E.get(B[i],0)+1
D=dict()
for i in range(N):
  if E[B[i]]&1:
    D[B[i]]=C
    C+=1
  else:
    D[B[i]]=-1
for i in range(N):
  if (i&1)!=(D[A[i]]&1) and D[A[i]]!=-1:
    P+=1
print(P>>1)

Solution (Python):
N = int(input())
A = []
ans = 0
for i in range(N):
  A.append([int(input()), i])
A.sort()
for idx, a in enumerate(A):
  if idx % 2 != a[1] % 2:
    ans += 1
print(ans//2)

Solution (Python):

import sys
def main(N, A):
    for j, (a, i) in enumerate(sorted([(a, i) for i, a in enumerate(A)], key=lambda x: x[0])):
        A[i] = j
    ans2 = sum((i + a) & 1 for i, a in enumerate(A))
    print(ans2 // 2)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]
    main(N, A)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    al = []
    od = [10**18]
    for i in range(n):
        a = int(ipt())
        al.append(a)
        if i&1:
            od.append(a)
    al.sort()
    od.sort()
    ans = 0
    oi = 0
    for i,ai in enumerate(al):
        if ai == od[oi]:
            if i&1 == 0:
                ans += 1
            oi += 1
    print(ans)

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

A = np.array(read().split(), np.int32)[1:]

to = A.argsort()

n = (to[::2] & 1).sum() + ((to[1::2] ^ 1) & 1).sum()
print(n // 2)

Solution (Python):
n=int(input())
a=[int(input())for i in range(n)]
l=sorted(a)[1::2]
a=a[::2]
print(len(set(a)&set(l)))

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

O = set(sorted(A)[::2])
E = set(sorted(A)[1::2])

ans = 0
for i in range(N):
    if i % 2 == 0 and A[i] not in O:
        ans += 1
    elif i % 2 == 1 and A[i] not in E:
        ans += 1
print(ans//2)

Solution (Python):
n=int(input())

ans=0

a=[]
b=[]

for _ in range(n):
    x=int(input())
    a.append(x)
    b.append(x)
b.sort()

dic={}
for i,v in enumerate(b):
    dic[v]=i%2

cnt=0
for i,v in enumerate(a):
    if i%2 != dic[v]:
        cnt+=1
print(cnt//2)

Solution (Python):
compress3 = lambda arr: list(map({e: i for i, e in enumerate(sorted(set(arr)))}.__getitem__, arr))
n = int(input())
a = [int(input()) for i in range(n)]
a = compress3(a)
odd = set()
even = set()

for i in range(n):
    if i % 2 == 0:
        even.add(a[i])
    else:
        odd.add(a[i])

ans = len(set([2*i for i in range(n//2)]) & odd)
ans = max(ans, len(set([2*i+1 for i in range(n//2)]) & even))
print(ans)

Solution (Python):
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
a=[]
for i in range(n):
  a.append([int(input()),i])
a=sorted(a, key=lambda m: m[0])
counter=0
for i in range(n):
  if (a[i][1]-i)%2==1:
    counter+=1
c=counter//2
if (c+1)*2<=counter:
  c+=1
print(c)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [None] * n
for i in range(n):
    a[i] = (i,int(input()))
    
a.sort(key=lambda x: x[1])
ans = 0
for i in range(n):
    if a[i][0]%2 != i%2:
        ans += 1
print(ans//2)

Solution (Python):
def main():
    n = int(input())
    a = [None]*n
    b = [None]*n
    for i in range(n):
        x = int(input())
        a[i] = x
        b[i] = x
    b.sort()
    dic = {}
    for i, v in enumerate(b):
        dic[v] = i
    cnt = 0
    for i in range(n):
        if i%2 != dic[a[i]]%2:
            cnt += 1
    print(cnt//2)

if __name__ == "__main__":
    main()

Solution (Python):
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
l=LN(n)
sl=sorted(l)
d={}
ans=0
for i,j in enumerate(sl):
    d[j]=i%2
for i,j in enumerate(l):
    if d[j]!=i%2:
        ans+=1
print(ans//2)

Solution (Python):
N=int(input())
D=[]
for i in range(N):
  x=int(input())
  D.append([x,i+1])

C=sorted(D)  
for i in range(N):
  C[i].append(i+1)

cnt=0
for a,b,c in C:
  if (abs(b-c))%2==1:
    cnt+=1
print(cnt//2)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = [NI() for _ in range(N)]
    B = copy.copy(A)
    B.sort()

    ans = 0
    for i in range(N):

        p = bisect.bisect_left(B,A[i])
        ans += (i - p) % 2
    print(ans//2)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=[int(input()) for i in range(N)]
    sorted_A=list(sorted(A))
    d={x:i for i,x in enumerate(sorted_A)}
    ans=0
    for i in range(N):
        if d[A[i]]%2!=i%2:
            ans+=1
    ans//=2
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n = int(readline())
a = [int(readline()) for i in range(n)]
k = [ai for i,ai in enumerate(a) if i%2 == 0]
k = set(k)
a.sort()
ans = 0
for i,ai in enumerate(a):
  if ai in k and i%2 == 1:
    ans += 1
print(ans)

Solution (Python):
N = int(input())
B = [[int(input()), i] for i in range(N)]
B.sort()
A = [0] * N
c = 0
for _, i in B:
  A[i] = c
  c += 1

ans = 0
for i, a in enumerate(A):
  diff = abs(i - a)
  if diff % 2:
    ans += 1

print(ans // 2)

Solution (Python):
N=int(input())
l=[]
for i in range(N):
    a=int(input())
    l.append([a,i])
l.sort(key=lambda x:x[0])
dif=[]
for i in range(N):
    dif.append(abs(l[i][1]-i)%2)

print(sum(dif)//2)

Solution (Python):
n=int(input())
a=[int(input()) for i in range(n)]
a2=[]
for i in range(n):
  if i%2==0:
    a2.append(a[i])
a2=set(a2)
A=sorted(a)
A2=[]
ct=0
for i in range(n):
  if i%2==0:
    if A[i] not in a2:
      ct+=1
print(ct)

Solution (Python):
import sys
import bisect
input = sys.stdin.readline

N = int(input())
As = [int(input()) for _ in range(N)]
sortedAs = sorted(As)

parity = 0
for i in range(1, N, 2):
    index = bisect.bisect_left(sortedAs, As[i])
    if index % 2 == 0:
        parity += 1

print(parity)

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

a.sort()

ans=0

for i in range(n):
    ans+=(a[i][1]-i)%2
print(ans//2)

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





N = inputI()
A = inputILs(N)

B = A[:]
A.sort()

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

print(len(a-b))

Solution (Python):
import sys

N = int(sys.stdin.readline().rstrip())

A = []
for _ in range(N):
    A.append(int(sys.stdin.readline().rstrip()))

odd_set = set()
for i in range(N):
    if i % 2 == 0:
        odd_set.add(A[i])

A.sort()
even_set = set()
for i in range(1, N, 2):
    even_set.add(A[i])



print(len(odd_set & even_set))

Solution (Python):
n=int(input())
a=[int(input())for i in range(n)]
b=a.copy()
b.sort()
ans=0
import bisect
for i,j in enumerate(a):
    k=bisect.bisect_left(b,j)
    if i%2!=k%2:
        ans+=1

print(ans//2)

Solution (Python):
n = int(input())
arr = []
base_left = set()
for i in range(n):
    a = int(input())
    arr.append(a)
    if i%2 == 0:
        base_left.add(a)

arr.sort()

left = set()
for i in range(n):
    if i %2 == 0:
        left.add(arr[i])

print(len(base_left-(base_left&left)))

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

dic={}
for i,a in enumerate(A):
    dic[a] = i

A.sort()
ans = 0
for i,a in enumerate(A):
    ans += (dic[a]-i)%2
print(ans//2)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
A = []
for i in range(n):
    a = int(input())
    A.append(a)
I = list(range(n))
I.sort(key = lambda x:A[x])
ans = 0
for i,j in enumerate(I):
    ans += (i-j)%2
print(ans//2)

Solution (Python):
n=int(input())
l=[(int(input()),i) for i in range(n)]
l.sort()
ans=0
for i in range(n):
    k,v=l[i]
    if (i+v)%2:ans+=1
print(ans//2)

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
d = {}
a = []
for i in range(n):
    aa = ni()
    d[aa] = i
    a.append(aa)

a.sort()
c = 0
for j in range(n):
    p = a[j]
    if (d[p]-j)%2 == 1:
        c += 1

print((c-1)//2+1)

Solution (Python):
N = int(input())
if N==1:
    print(0)
else:
    l1 = []
    for i in range(N):
        a = int(input())
        l1.append(a)
    l2 = sorted(l1)
    d1 = {j:i for i,j in enumerate(l1)}
    d2 = {j:i for i,j in enumerate(l2)}
    ans = 0
    for i in d1.keys():
        ans += (d1[i]%2!=d2[i]%2)
    ans //= 2
    print(ans)

Solution (Python):
INF = 10 ** 15
MOD = 10 ** 9 + 7 

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A = list(enumerate(A))
    A.sort(key = lambda x:x[1])
    ans = 0
    for i,(j,v) in enumerate(A):
        ans += (j - i)%2
    print(ans//2)
if __name__ == '__main__':
    main()

Solution (Python):
import sys


def compress(aaa):
    s = sorted(set(aaa))
    d = {a: i for i, a in enumerate(s)}
    return d, list(map(d.get, aaa))


n, *aaa = map(int, sys.stdin.buffer.read().split())

d, aaa = compress(aaa)
ans = 0
for i, a in enumerate(aaa):
    ans += (i ^ a) & 1
print(ans // 2)

Solution (Python):
n=int(input())
a=[int(input()) for i in range(n)]
b=sorted(a)
a0=[]
b0=[]
for i in range(n):
    if i%2==0:
        a0.append(a[i])
        b0.append(b[i])
print(len(a0)-len(list(set(a0) & set(b0))))