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):
import numpy as np
n = int(input())
a = np.array([int(input()) for _ in range(n)])
b = np.argsort(a)


print(sum(b[::2]%2))

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

Solution (Python):
import math

N = int(input())

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

idx_A = {}
for i in range(N):
    idx_A[A[i]] = i

B = tuple(sorted(A))

"""
ソート後の位置までの距離が奇数だと操作１が一回必要になる
一度の操作１で最大で２個までのソート後の位置までの距離が奇数のものを偶数にずらしてあげられる
ので、正しい位置までの距離が奇数のものの個数をしらべて、最小の操作１の回数を求める
"""
cnt = 0
for i in range(N):
    if abs(i - idx_A[B[i]]) % 2 == 0: 
        continue
    else:
        cnt += 1


print(math.ceil(cnt/2))

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
Ao = set(A[1::2])
Aos = set(sorted(A)[1::2])

print(len(Aos - Ao))

Solution (Python):
def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    b = sorted(a)
    c = b[::2]
    d = a[::2]
    set_c = set(c)
    set_d = set(d)
    print(len(set_c - set_d))
main()

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

Solution (Python):
def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    b = sorted(a)
    set_c = set(b[::2])
    set_d = set(a[::2])
    print(len(set_c - set_d))
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    b = sorted(a)
    c = b[::2]
    d = a[::2]
    set_c = set(c)
    set_d = set(d)
    print(len(set_c - set_d))
main()

Solution (Python):
N=int(input())
A= [int(input()) for i in range(N)]
B=sorted(A)
tmp=0
j=0
a=set(A[::2])
b=set(B[::2])
print(len(a-b))

Solution (Python):
N=int(input())
A=[[int(input()),i,0] for i in range(N)]


A.sort()
for i in range(N):
  A[i][2]=i


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


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

Solution (Python):
import sys
import heapq
import bisect
import itertools

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def LI_(): return([int(x)-1 for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    N = I()
    A = IR(N)

    i = 0
    odd_start = [A[i] for i in range(0,N,2)]
    A.sort()
    even_end = [A[i] for i in range(1,N,2)]

    count_list = odd_start + even_end
    count_list.sort()

    ans = 0

    for i in range(len(count_list)-1):
        if count_list[i] == count_list[i+1]:
            ans += 1
    return(ans)
    

if __name__ == "__main__":
    print(main())

Solution (Python):
from heapq import heappop, heappush
N = int(input())
A = []
memo = {}
count = 0
for i in range(N):
  a = int(input())
  if i%2 == 1:
    memo[a] = 1
  else:
    memo[a] = 0
  heappush(A,a)

for i in range(N):
  x = heappop(A)
  if i%2 != memo[x]:
    count += 1
print(count//2)

Solution (Python):
from heapq import heappop, heappush
N = int(input())
idx = {}
A = []
ans = 0
for i in range(N):
  a = int(input())
  idx[a] = i%2
  heappush(A,a)

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST(N)
A2 = sorted(A)


A_mod = {}
A2_mod = {}
for i in range(N):
    A_mod[A[i]] = i % 2
    A2_mod[A2[i]] = i % 2

cnt = 0
for k, v in A_mod.items():
    
    if v != A2_mod[k]:
        cnt += 1
print(cnt//2)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = [0]*N
    r = 0
    for i in range(N):
        a = int(input())
        A[i] = (a, i)
    A.sort()
    cnt = 0
    for i in range(0, N, 2):
        a, j = A[i]
        cnt += j & 1
    print(cnt)

main()

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

ki = set()

for i in range(0, n, 2):
    ki.add(a[i])

ans = 0
a.sort()
for i in range(1, n, 2):
    if a[i] in ki:
        ans += 1
print(ans)

Solution (Python):
N = int(input())
As = []
for i in range(N):
  A = int(input())
  As.append(A)
Is1 = sorted(range(N), key=lambda i: As[i])
Is = [-1]*N
for i in range(N):
  Is[Is1[i]] = i


r = 0
for i in range(N):
  j = Is[i]
  if (j-i)%2 == 1:
    r += 1
r = r//2
print(r)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():

    return


def B():
    n = I()
    a = IR(n)
    ans = 0
    b = [0]*(n+1)
    for i in range(n):
        ans += (a[i]+b[i])>>1
        if (a[i]%2)^(b[i]%2) and a[i]:
            b[i+1] += 1
    print(ans)
    return


def C():
    n = I()
    a = IR(n)
    b = [(a[i],i) for i in range(n)]
    b.sort()
    for i in range(n):
        a[b[i][1]] = i+1
    ans = 0
    for i in range(n):
        if a[i]&1 == i&1:
            ans += 1
    print(ans>>1)
    return


def D():

    return


def E():

    return


def F():

    return


if __name__ == "__main__":
    C()

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

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

eo = [0]*2

As = sorted(A)
for i in range(N):
    if i % 2 != bisect.bisect_left(As, A[i]) % 2:
        eo[i % 2] += 1

print(max(eo))

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
x = set(A[::2])
y = set(sorted(A)[::2])
print(len(x)-len(x&y))

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]
b = sorted(a)
cnt = 0
for i in range(n):
    if a[i] != b[i]:
        r = bl(b,a[i])
        if i % 2 ^ r % 2 == 0:
            continue
        cnt += 1
print(cnt//2)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]
b = sorted(a)
lst = []
for i in range(n):
    if a[i] != b[i]:
        r = bl(b,a[i])
        if i % 2 ^ r % 2 == 0:
            continue
        lst.append(a[i])
m = len(lst)
ans = m//2
print(ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]
b = sorted(a)
lst = []
for i in range(n):
    if a[i] != b[i]:
        r = bl(b,a[i])
        if i % 2 ^ r % 2 == 0:
            continue
        lst.append(a[i])
lst.sort()
m = len(lst)
ans = m//2
print(ans)

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




B = sorted(A)
sortedIndex = {b : i for i, b in enumerate(B)}

ans = 0
for i, a in enumerate(A):
    if i % 2 != sortedIndex[a] % 2:
        ans += 1

print(ans // 2)

Solution (Python):
import bisect

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

SA = sorted(A)
ans = 0
for i in range(N):
  rank = bisect.bisect_left(SA,A[i])
  
  if (i + rank) % 2 == 1:
    ans += 1
print(ans//2)

Solution (Python):
import bisect as bi
n=int(input())
b=[0]*n
c=[0]*n
ans=0
for i in range(n):
    r=int(input())
    b[i]=[r,i%2]
    c[i]=r
c.sort()
for i in range(n):
    j=bi.bisect_left(c,b[i][0])
    
    ans+=abs(j%2-b[i][1])
print(ans//2)

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

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

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

def main():
    N = int(input())
    a = []

    for i in range(N):
        n = int(input())
        a.append([n, i])
    
    a = sorted(a)

    ans = 0
    for i in range(N):
        _, index = a[i]
        if i&1 != index&1:
            ans += 1
    print(ans//2)

if __name__ == "__main__":
    main()

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

sorted_a  = sorted(a)
set_a = set(a[::2])
set_sorted_a = set(sorted_a[::2])

print(len(set_a ^ set_sorted_a) // 2)

Solution (Python):
import sys
input = sys.stdin.readline
n=int(input())
A=[]
append=A.append
for i in range(n):
  append((int(input()),i+1))
A.sort(key=lambda x:x[0])
ans=0
for i in range(n):
  a,b=A[i]
  if (i+1)%2!=b%2:
    ans+=1
print(ans//2)

Solution (Python):
import numpy as np
N=int(input())
A=[]
for _ in range(N):
  A.append(int(input()))

A_sort_index=np.argsort(A)
ans=0

for i in range(N):
  if (A_sort_index[i]-i)%2==1:
    ans+=1

if ans%2==0:
    ans=ans//2
else:
    ans=ans//2+1
  
print(ans)

Solution (Python):
n = int(input())
a = [int(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)

Solution (Python):
N = int(input())
A_raw = [0] * N
for i in range(N):
    A_raw[i] = (int(input()), i)
A_raw.sort(key=lambda x: x[0])
A = [0] * N
for i in range(N):
    A[A_raw[i][1]] = i

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

print(ans)

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

"""
奇数番目集合、偶数番目集合の中で自由にできるのが操作2．
操作1で集合間のやりとりをする
"""

import numpy as np

N = int(input())
A = np.fromstring(sys.stdin.read(),dtype=np.int64,sep='\n')

B = np.sort(A)

answer = len(np.setdiff1d(A[::2],B[::2]))
print(answer)

Solution (Python):

def main():
    
    
    
    N, *A = map(int, open(0).read().split())
    S = sorted(A)
    dif = set(A[::2]) ^ set(S[::2])
    
    ans = len(dif) // 2
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def main():
    
    
    
    N, *A = map(int, open(0).read().split())
    S = sorted(A)
    dif = set(A[::2]) ^ set(S[::2])
    
    ans = len(dif) // 2
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def main():
    N, *A = map(int, open(0).read().split())
    S = sorted(A)
    dif = set(A[::2]) ^ set(S[::2])
    ans = len(dif) // 2
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import bisect
import copy
n = int(input())
L = []
zahyou = []
for i in range(n):
    L.append(int(input()))
C = copy.deepcopy(L)
C.sort()
for i in range(n):
    t = L[i]
    k = bisect.bisect_left(C,t)
    zahyou.append(k)
ans = 0
for i in range(n):
    if zahyou[i]%2 != i%2:
        ans += 1
print(ans//2)

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

N = int(input())
L = [int(input()) for _ in range(N)]
d = {l: i % 2 for i, l in enumerate(L)}

sorted_L = sorted(L)
d_s = {l: i % 2 for i, l in enumerate(sorted_L)}

cnt = 0
for l in L:
    if d_s[l] == d[l]:
        continue
    else:
        cnt += 1
print(cnt//2)

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

Solution (Python):
N = int(input())
A = [0] * (N+1)

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

sorted_A = sorted(A)
sorted_dict_A = { sorted_A[i]: i for i in range(1, N+1) }

cnt = 0
for i in range(1, N+1):
    ind = sorted_dict_A[A[i]]
    if ind % 2 != i % 2:
        cnt += 1

print(cnt // 2)

Solution (Python):
n = int(input())
a = [[int(input()),i] for i in range(n)]
a.sort()
ans = 0
for i,tmp in enumerate(a):
  x,j = tmp
  ans += abs(i-j) % 2
print(ans//2)

Solution (Python):
from operator import itemgetter

n = int(input())
a = []

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

a.sort(key=itemgetter(1))

ans = 0
for i in range(n):
    ans += abs(a[i][0]-i)%2

print(ans//2)

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

Solution (Python):
n = int(input())
num_list = [ (int(input()),i+1) for i in range(n) ]
num_list_2 = sorted(num_list)
num_list_3 = [ (num_list_2[i][0],num_list_2[i][1],i+1) for i in range(n) ]

ans = sum([ abs(i[1] - i [2]) % 2 for i in num_list_3]) // 2
print(ans)

Solution (Python):
n=int(input())
arr=[[int(input()),i+1] for i in range(n)]
arr=sorted(arr,key=lambda x:x[0])
for i in range(n):
  arr[i].append(i+1)
ans=0
for val,pos1,pos2 in arr:
  if abs(pos1-pos2)%2==1:
    ans+=1
  else:
    continue
print(ans//2)

Solution (Python):
n=int(input());a=sorted([[int(input()),i]for i in range(n)]);print(sum([(a[i][1]-i)%2for i in range(n)])//2)

Solution (Python):
a=sorted([[int(input()),i]for i in range(int(input()))]);print(sum([(a[i][1]-i)%2for i in range(len(a))])//2)

Solution (Python):

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



R = {a: i for i, a in enumerate(sorted(A))}
ans = sum(i % 2 != R[a] % 2 for i, a in enumerate(A)) // 2


print(ans)

Solution (Python):

from collections import defaultdict

def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    B = sorted(A)
    d = defaultdict( int)
    for i in range(N):
        d[B[i]] = i
    odd = 0
    for i in range(N):
        if (i+1)%2 == d[A[i]]%2 and d[A[i]]%2 == 1:
            odd += 1
    print(odd)
    
if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict

def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    B = sorted(A)
    d = defaultdict( int)
    for i in range(N):
        d[B[i]] = i
    odd = 0
    for i in range(N):
        if (i+1)%2 == d[A[i]]%2 and d[A[i]]%2 == 1:
            odd += 1
    print(odd)
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict
input = sys.stdin.readline
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    B = sorted(A)
    d = defaultdict( int)
    for i in range(N):
        d[B[i]] = i
    odd = 0
    for i in range(N):
        if (i+1)%2 == d[A[i]]%2 and d[A[i]]%2 == 1:
            odd += 1
    print(odd)
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict
input = sys.stdin.readline
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    B = sorted(A)
    d = defaultdict( int)
    for i in range(N):
        d[B[i]] = i
    odd = 0
    for i in range(N):
        if (i+1)%2 == d[A[i]]%2 and d[A[i]]%2 == 1:
            odd += 1
    print(odd)
    
if __name__ == '__main__':
    main()

Solution (Python):
s = int(input())
a = []
b = []
o = 0
count = 0
for j in range(s):
        if j%2 == 0:
                a.append(int(input()))
        else:
                b.append(int(input()))
a = sorted(a)
c = sorted(a+b)
for i in range(s):
        if o == len(a):
                break
        if a[o] == c[i]:
                if i%2 == 1:
                        count += 1
                o += 1
print(count)

Solution (Python):
N=int(input())
A=[]
B=[]
for i in range(N):
	if i%2==0:
		A.append(int(input()))
	else:
		B.append(int(input()))
		
A=sorted(A)
B=sorted(B)
C=sorted(A+B)

c=0
j=0
for i in range(N):
	if j>=len(A):
		break
	if A[j]==C[i]:
		if i%2==1:
			c+=1
		j+=1
print(c)

Solution (Python):
n,*a=map(int,open(0).read().split());print(len(set(a[::2])^set(sorted(a)[::2]))//2)

Solution (Python):





from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)


def main():
    n,*a=map(int,open(0).read().split())
    b=set(a[::2])
    c=set(sorted(a)[::2])
    print(len(b^c)//2)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    X = Counter(sorted(A[::2]))
    Y = Counter(sorted(A)[::2])
    K = set(list(X.keys()) + list(Y.keys()))
    diff = 0
    for k in K:
        tmp = 0
        if k in X:
            tmp += X[k]
        if k in Y:
            tmp -= Y[k]
        diff += abs(tmp)
    print(diff//2)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
l = [int(input()) for _ in range(n)]
bef,aft = {},{}
cnt =  0
for i in range(n):
  bef[l[i]] = i%2
l.sort()
for i in range(n):
  aft[l[i]] = i%2
for x in l:
  if bef[x]^aft[x]:
    cnt += 1
print(cnt//2)

Solution (Python):
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

N = int(input())
A = [int(input()) for _ in range(N)]
C = Counter(A[::2])
D = Counter(sorted(A)[::2])
ans = 0

for k, v in D.items():
    ans += max(0, v - C[k])
print(ans)

Solution (Python):
import bisect
a=[]
x=0
for i in range(int(input())):a.append(int(input()))
b=sorted(a)
for i,j in enumerate(a):
    if i%2==1:continue
    elif bisect.bisect_left(b,j)%2==1:x+=1
print(x)

Solution (Python):
import itertools
N = int(input())
A = list(enumerate([int(input()) for _ in range(N)]))
B = [iv[0] for iv in sorted(
    enumerate([i for i, v in sorted(A, key=lambda xs: xs[1])]),
    key=lambda xs: xs[1])]
print(sum(b % 2 == 0 for b in B[1::2]))

Solution (Python):
import itertools
N = int(input())
A = list(enumerate([int(input()) for _ in range(N)]))
B = [iv[0] for iv in sorted(
    enumerate([i for i, v in sorted(A, key=lambda xs: xs[1])]),
    key=lambda xs: xs[1])]
print(sum(b % 2 for b in B[::2]))

Solution (Python):
from collections import defaultdict as d
a=[int(input()) for i in range(int(input()))]
b=sorted(a)
c=d(int)
e=0
for i in b[::2]:
    c[i]=1
for i in a[1::2]:
    e+=c[i]
print(e)

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

A.sort()
ans = 0
for j in range(n):
    if (j%2) != (A[j][1]%2):
        ans += 1

print(ans//2)

Solution (Python):


n=int(input())
a,b,c=[],[],[]
f=0
for i in range(n):
    x=int(input())
    a.append(x)
    if f==0:
        b.append(x)
    else:
        c.append(x)
    f=1-f

a.sort()

d=a[1:n:2]
sc=set(c)
sd=set(d)
ans=len(sd-sc)
print(ans)

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

B=sorted(A)

C=[]
D=[]

for i in range(N):
    if i%2==0:
        C.append(A[i])
        D.append(B[i])
        
print((N+1)//2-len(set(C) & set(D)))

Solution (Python):
from copy import deepcopy
N = int(input())
A = [int(input()) for n in range(N)]
Aorder = deepcopy(A)
Aorder.sort()
odd, even = set(), set()
for i in range(N):
    if i % 2 == 0:
        even |= {Aorder[i]}
    else:
        odd |= {Aorder[i]}

missmatch = 0
for i in range(N):
    if i % 2 == 0:
        if A[i] in odd: missmatch += 1
    else:
        if A[i] in even: missmatch += 1
print(missmatch//2)

Solution (Python):
import copy

n = int(input())

nums = []
for i in range(n):
    nums.append(int(input()))

taiou = {}
reprica = copy.copy(nums)
reprica.sort()
for i, r in enumerate(reprica):
    taiou[r] = i
ans = 0
for i, num in enumerate(nums):
    if i % 2 != taiou[num] % 2:
        ans += 1

print(ans // 2)

Solution (Python):


import sys

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    A = [II() for _ in range(n)]

    B = A[:]
    A.sort()

    return (n + 1) // 2 - len(set(A[::2]) & set(B[::2]))


print(main())

Solution (Python):
n = int(input())
info =[]

for i in range(n):
  info.append([int(input()),i])
info = sorted(info)
  
ans = 0
for i in range(n):
  if i%2 != info[i][1]%2:
    ans = ans+1
print(ans//2)

Solution (Python):
import bisect
N = int(input())
L = []
def index(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return True
    else:
        return False
for i in range(N):
    L.append(int(input()))
L0 = L[::2]
L.sort()
Ls0 = L[::2]
cc = 0
for i in range((N+1)//2):
    if not index(Ls0, L0[i]):
        cc += 1
print(cc)

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

O=[]
E=[]
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
    if i%2==0:
        O.append(a)
    else:
        E.append(a)
        
A.sort()
Odd=0
Eve=0
for i in range(len(O)):
    if bisect.bisect_left(A,O[i])%2==0:
        Odd+=1
    else:
        Eve+=1
print(Eve)

Solution (Python):
N=int(input())
a=[int(input()) for i in range(N)]
b=sorted(a)
d={}
for i in range(N):
  d[b[i]]=i
for i in range(N):
  a[i]=d[a[i]]
ans=0
for i in range(N):
  if i%2==0 and a[i]%2==1:
    ans+=1
print(ans)

Solution (Python):
import sys
N = int(input())
S = []
for i in range(N):
    a = int(input())
    S.append((a,i))
S.sort()
T = [0]*(N)
for i in range(N):
    T[S[i][1]] = i
if N == 1:
    print(0)
    sys.exit()
ans = 0
for i in range(0,N,2):
    if T[i]%2:
        ans += 1
print(ans)

Solution (Python):
n = int(input())
a = []
for i in range(n):
  x = int(input())
  a.append(x)
zi = {}
b= sorted(a)
for i in range(n):
  zi[b[i]] = i
g = 0
k = 0
for i in range(n):
  if zi[a[i]] %2 == i%2:
    continue
  elif i%2 == 1:
    g += 1
  else:
    k += 1
print(g)

Solution (Python):





"""
agc 003
"""

from operator import itemgetter

n = int(input())
ali = [int(input()) for i in range(n)]
sortedali = sorted(enumerate(ali), key=itemgetter(1))

ansdouble = 0
for (i, (j, _)) in enumerate(sortedali):
    if (i-j) % 2 != 0:
        ansdouble += 1

print(ansdouble//2)

Solution (Python):
from bisect import bisect
N=int(input())
A=set()
B=set()
C=[]
for i in range(N):
    s=int(input())
    if i%2==0:
        A.add(s)
    else:
        B.add(s)
    C.append(s)
C.sort()
ans=0
for i in range(N):
    s=C[i]
    if i%2==0:
        if s not in A:
            ans+=1        
print(ans)

Solution (Python):
import bisect
n=int(input())
l=[]
e=[]
for i in range(n//2):
    j=int(input())
    e.append(j)
    l.append(j)
    j=int(input())
    l.append(j)
if n%2==1:
    j=int(input())
    e.append(j)
    l.append(j)
l.sort()
e.sort()
res=0
for i in range(0,n,2):
    if e[min(len(e)-1,bisect.bisect_left(e,l[i]))]!=l[i]:
        res+=1
print(res)

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

a = []

for i in range(n):
    a.append([int(input()), i])
    
a = sorted(a, key = lambda x:x[0])
ans = 0

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

Solution (Python):
n=int(input())
a=[int(input()) for i in range(n)]
a2=set(a[::2])
a.sort()
a3=set(a[::2])
print(len(a2^a3)//2)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

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

cnt = defaultdict(lambda:[0,0])
for i,a in enumerate(aa):
    if i%2 == 0:
        cnt[a][0] += 1
    else:
        cnt[a][1] += 1

aa.sort()
ans = 0
for i,a in enumerate(aa):
    ev,od = cnt[a]
    if i%2 == 0:
        if ev == 0:
            ans += 1
            cnt[a][0] -= 1
        else:
            cnt[a][1] -= 1
    else:
        if od == 0:
            ans += 1
            cnt[a][0] -= 1
        else:
            cnt[a][1] -= 1

print(ans//2)

Solution (Python):
print sum(a[1]%2for a in sorted((input(),i)for i in range(input()))[::2])

Solution (Python):
print(sum(a[1]%2for a in sorted((int(input()),i)for i in range(int(input())))[::2]))

Solution (Python):
n=int(input());a=sorted((int(input()),i)for i in range(n));print(sum(a[i][1]%2for i in range(0,n,2)))

Solution (Python):
n,*a=map(int,open(0).read().split())
b={}
c=0
for i,t in zip(range(n),sorted(a)):
  b[t]=i%2
for i,t in zip(range(n),a):
  c+=i%2!=b[t]
print(c//2)

Solution (Python):
n,*a=map(int,open(0).read().split())
b={}
c=0
for i,t in zip(range(n),sorted(a)):
  b[t]=i%2
for i,t in zip(range(n),a):
  c+=i%2!=b[t]
print(c//2)

Solution (Python):


INF = float('inf')


def inpl(): return list(map(int, input().split()))


N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A)
C = A[::2] + B[1::2]
D = set(C)

print(N - len(D))

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_left

dic = dict()

n = ni()
a = []
for _ in range(n):
    a.append(ni())
    
b = sorted(a)

for i, ai in enumerate(a):
    dic[ai] = (i, bisect_left(b,ai))
    
cnt = 0
for ord1, ord2 in dic.values():
    if ord1%2 != ord2%2:
        cnt += 1
        
print(cnt // 2)

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

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]
As = sorted(A)
Ass = set(As[::2])
cnt = 0
for a in A[::2]:
    if a not in Ass:
        cnt += 1
print(cnt)

Solution (Python):
import bisect
n = int(input())
a=[int(input()) for i in range(n)]
b = sorted(a)
for i in range(n):
    k = bisect.bisect_left(b,a[i])
    a[i]= k

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

print(ass//2)

Solution (Python):
N=int(input())
A=[int(input()) for i in range(N)]
AT=[(A[i],i) for i in range(N)]
AT.sort()
B=[AT[i][1] for i in range(N)]
X=[[0,0],[0,0]]
for i in range(N):
    X[i%2][B[i]%2]+=1
Y=[X[0][1],X[1][0]]
print(min(Y))

Solution (Python):
import numpy as np
N=int(input())
A=[int(input()) for i in range(N)]
B=list(np.argsort(np.array(A)))
X=[[0,0],[0,0]]
for i in range(N):
    X[i%2][B[i]%2]+=1
print(X[0][1])

Solution (Python):
import numpy as np
N=int(input())
A=[int(input()) for i in range(N)]
B=list(np.argsort(np.array(A)))
X=[[0,0],[0,0]]
for i in range(N):
    X[i%2][B[i]%2]+=1
Y=[X[0][1],X[1][0]]
print(min(Y))

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
even = set(sorted(A[::2]))
A_sorted = sorted(A)
even_sorted = set(A_sorted[::2])
print(len(even) - len(even & even_sorted))

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

As.sort()


print(len([A for A, i in As[::2] if i % 2]))

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N = read()
A = []
for _ in range(N):
  A.append(read())
B = sorted(A)
d = {B[i] : i for i in range(N)}
ans = sum((d[A[i]] ^ i) & 1 for i in range(N)) // 2
print(ans)