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



Sample input:
4
2
4
3
1


Sample output:
1

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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  # from_index と to_index の差が奇数であるものの個数
    for a in A:
        if abs(from_index[a] - to_index[a]) % 2 == 1:
            cnt += 1
    print(cnt // 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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:
    # print(C[ai],i)
    if i % 2 == 0:
      odd += 1
    else:
      even += 1
m = min(odd,even)
odd -= m
even -= m
count += m
count += max(odd,even)
# print(C.items())
print(count)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

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

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()))


# ===CODE===

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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

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()))
# rstrip().decode()


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()

Submission status: Accepted

Solution code:
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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

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]))

Submission status: Accepted

Solution code:
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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)
# print(ki,gu)
# print(so)
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
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)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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(dif)
print(sum(dif)//2)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
n=int(input())
a=[(int(input()),i) for i in range(n)]
#print(a)
a.sort()
#print(a)
ans=0

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

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


#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
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)]

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

######Combination######
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

######Factorization######
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

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

#############
# Main Code #
#############

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))

Submission status: Accepted

Solution code:
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(odd_set)
# print(even_set)

print(len(odd_set & even_set))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)