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:
import sys
input = sys.stdin.readline

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

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

A.sort()

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
d = [{x: 0 for x in a} for _ in range(2)]
b = sorted(a)
for i in range(n):
    if i % 2:
        d[0][a[i]] += 1
        d[1][b[i]] += 1
t1 = 0
t2 = 0
for v1, v2 in zip(d[0].values(), d[1].values()):
    if v1 > v2:
        t1 += v1 - v2
print(t1)

Submission status: Accepted

Solution code:
N = int(input())
ans = 0
if N % 2 == 1:
    A = [0]*N
    for i in range(N):
        A[i] = int(input())
else:  # 要素数を擬似的に奇数にして後の操作を楽にする
    N += 1
    A = [0] * N
    A[N-1] = 10**9+1
    for p in range(N-1):
        A[p] = int(input())
even = set()
for k in range(N//2+1):
    even.add(A[2*k])
# print(even)
B = sorted(A)
for j in range(N // 2):
    if B[(2 * j)+1] in even:
        ans += 1
        #print(A[2 * j])

print(ans)
# print(A)

Submission status: Accepted

Solution code:
#%%
n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    tmp = [int(input()), i]
    a[i] = tmp

b = sorted(a)
#print(b)

c = []
ans = 0
for i in range(n):
    c.append(b[i][1])
    ans += (i - c[i])%2
ans //= 2

print(ans)

Submission status: Accepted

Solution code:
import bisect

def main():
    n = int(input())
    l = [[i,int(input())] for i in range(n)]
    l.sort(key=lambda x:x[1])
    res =0
    for i in range(n):
        if i % 2 != l[i][0] % 2:
            res += 1
    print(res // 2)


main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[]

  for i in range(n):
    l.append([i,I()])

  l2=copy.deepcopy(l)

  l2=sorted(l2,key=lambda x:x[1])

  ans=0
  for i,x in enumerate(l2):
    if i%2!=x[0]%2:
      ans+=1
  return ans//2

# main()
print(main())

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:
n=int(input())
A = [0]*(n)
for i in range(n):
    s=int(input())
    A[i]=[s,i]    
lista=sorted(A,key=lambda x:x[0])
cnt=0
for i in range(n):
    lista[i].append(i)
for i in range(n):
    if (lista[i][1]-lista[i][2])%2!=0:
        cnt+=1
print(cnt//2)

Submission status: Accepted

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


def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    before = list()
    after = list()

    # 操作1を行う必要があるのは，
    # 操作をする前と条件を満たすよう操作した後で
    # 各要素の位置の偶奇が不一致のときではないか?
    for index, ai in enumerate(a, 1):
        before.append((ai, index % 2))

    for index, ai in enumerate(sorted(a), 1):
        after.append((ai, index % 2))

    count = 0

    for b, a in zip(sorted(before), after):
        if b[1] != a[1]:
            count += 1

    # 1回の操作で，2個の位置を変えられる
    print(count // 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

A = []

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

A.sort()

for i in range(N):
    A[i].append(i+1)


ans = 0
for i in range(N):
    num, before, after = A[i]
    if before % 2 != after % 2:
        ans += 1

print(ans//2)

Submission status: Accepted

Solution code:
# 2019/10/03

import sys

inpt=sys.stdin.readline
n=int(input())
a=[]
for i in range(n):
    a.append((int(input()),i+1))
a.sort()

cnt=0
for idx,aa in enumerate(a,1):
    if aa[1]%2==idx%2:continue
    cnt+=1
print(cnt//2)

Submission status: Accepted

Solution code:
N = int(input())
A = [[i%2, int(input())] for i in range(N)]
A = sorted(A,key=lambda x: x[1])

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

ans = cnt // 2
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = np.array([int(input()) for _ in range(n)])
b = np.argsort(a)
#print(b)
#print(b%2)
print(sum(b[::2]%2))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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():
    # 位置の偶奇の合わない所は操作1を使うことになる
    if v != A2_mod[k]:
        cnt += 1
print(cnt//2)

Submission status: Accepted

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

Submission status: Accepted

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

ki = set()

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

Submission status: Accepted

Solution code:
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
#print(As)
#print(Is)
r = 0
for i in range(N):
  j = Is[i]
  if (j-i)%2 == 1:
    r += 1
r = r//2
print(r)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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

#A
def A():

    return

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

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

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#AGC3 C

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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#AGC3 C

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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#AGC3 C

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)

Submission status: Accepted

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

# 操作2は0番目からの距離のmodが変化しない
# modが異なる数 / 2が答え

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)

Submission status: Accepted

Solution code:
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])
  #print(rank,A[i])
  if (i + rank) % 2 == 1:
    ans += 1
print(ans//2)

Submission status: Accepted

Solution code:
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])
    #print(j)
    ans+=abs(j%2-b[i][1])
print(ans//2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# AGC003C - BBuBBBlesort!
def main():
    # reverse three elements <-> reverse left and right ones
    # -> the parities of indices of A doesn't change
    # find Ai which has different parities of indices in A and S
    N, *A = map(int, open(0).read().split())
    S = sorted(A)
    dif = set(A[::2]) ^ set(S[::2])
    # odd in A but even in S & even in A but odd in S -> // 2
    ans = len(dif) // 2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AGC003C - BBuBBBlesort!
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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 入力
N = int(input())
A = [int(input()) for _ in range(N)]

# 奇数番目の要素が偶数番目に小さい、または、
# 偶数番目の要素が奇数番目に小さいならばその要素に対して操作1を適用する必要がある
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
#ここまでNlogN
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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()
#b=a[0:n:2]
d=a[1:n:2]
sc=set(c)
sd=set(d)
ans=len(sd-sc)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding:utf-8

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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