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())
if N==1:
    print(0)
else:
    l1 = []
    for i in range(N):
        a = int(input())
        l1.append(a)
    l2 = sorted(l1)
    d1 = {j:i for i,j in enumerate(l1)}
    d2 = {j:i for i,j in enumerate(l2)}
    ans = 0
    for i in d1.keys():
        ans += (d1[i]%2!=d2[i]%2)
    ans //= 2
    print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 15
MOD = 10 ** 9 + 7 

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

Submission status: Accepted

Solution code:
import sys


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


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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
n=int(input())
a=[int(input()) for i in range(n)]
b=sorted(a)
a0=[]
b0=[]
for i in range(n):
    if i%2==0:
        a0.append(a[i])
        b0.append(b[i])
print(len(a0)-len(list(set(a0) & set(b0))))

Submission status: Accepted

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

A = sorted(A,key = lambda x:x[0])

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from bisect import bisect_left

n, *a = map(int, read().split())
b = sorted(a)
cnt = 0
for i, aa in enumerate(a):
    if abs(i - bisect_left(b, aa)) % 2 == 1:
        cnt += 1
print(cnt // 2)

Submission status: Accepted

Solution code:
n = int(input())
kl = []
for i in range(n):
    a = int(input())
    kl.append(a)
from collections import defaultdict
dic = defaultdict(int)

for idx, i in enumerate(sorted(kl)):
    dic[i] = idx + 1
cl = [k for k in kl]

al = []
bl = []
for i, c in enumerate(cl):
    if i % 2 == 0:
        al.append(c)
    else:
        bl.append(c)


ans = 0
for b in bl:
    if dic[b] % 2 != 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = [int(input()) for _ in range(n)]
b = list(a)
b.sort()
s, t = 0, 0
for i in range(n):
    x = bisect.bisect_left(b, a[i])
    if i % 2 == 0 and x % 2 == 1:
        s += 1
    elif i % 2 == 1 and x % 2 == 0:
        t += 1
print(max(s, t))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N = int(input())
    A = [(int(input()), n % 2) for n in range(N)]
    A.sort()

    res = 0
    for i, (_, j) in enumerate(A):
        if i % 2 != j:
            res += 1

    print(res // 2)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy

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

a=copy.copy(A)
A.sort()
dic={}
for i in range(0,N):
    dic[a[i]]=0
    dic[a[i]]=i

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
b = {}
for i, j in enumerate(sorted(a)):
    b[j] = i
ans = 0
for i, j in enumerate(a):
    ans += (b[j] - i) % 2
print(ans // 2)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) * N + i for i in range(N)]
A.sort()
cnt = 0
for i in range(N):
  d = (A[i] % N) % 2
  if d % 2 != i % 2:
    cnt += 1
print(cnt//2)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
d={}
B=sorted(A)
for i in range(N):
    d[B[i]]=i
cnt=0
for i in range(N):
    if abs(i-d[A[i]])%2==1:
        cnt+=1
print(cnt//2)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = [(int(input()), i) for i in range(1, N+1)]
A.sort()
c = 0
for i, (a, j) in enumerate(A, 1):
    c += (i-j)&1
print(c//2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = IR(n)
    d = defaultdict(int)
    b = a[::1]
    b.sort()
    for i, bi in enumerate(b):
        d[bi] = i
    ans = [0, 0]
    for i in range(n):
        ans[i & 1] += d[a[i]] & 1 != i & 1
    print(max(ans))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#003_C
from bisect import bisect_left, bisect_right
n = int(input())
a = [int(input()) for _ in range(n)]
b = sorted(a)

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

Submission status: Accepted

Solution code:
def coord_compress(A):
    B = {a: i for i, a in enumerate(sorted(set(A)), 1)}
    return [B[a] for a in A]

N = int(input())
A = [int(input()) for _ in range(N)]
A = coord_compress(A)
A_odd, A_even = A[::2], A[1::2]
ans = 0
for a in A_odd:
    if a % 2 == 0: ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
As = [(int(input()),i) for i in range(N)]
As.sort()
cnt = 0
for i,(n, j) in enumerate(As):
    if j%2 != i%2:
        cnt += 1
    # print("aaa",n,i,cnt)
print(cnt//2)

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    if "W" in S and not "E" in S:
        print("No")
    elif "E" in S and not "W" in S:
        print("No")
    elif "N" in S and not "S" in S:
        print("No")
    elif "S" in S and not "N" in S:
        print("No")
    else:
        print("Yes")
    return

def examB():
    N = I()
    A = [I()for _ in range(N)]
    ans = 0
    for i in range(N-1):
        ans += A[i]//2
        if A[i]%2 and A[i+1]>=1:
            ans += 1
            A[i+1] -= 1
    ans += A[N-1]//2
    print(ans)
    return

def examC():
    N = I()
    A = [I()for _ in range(N)]
    if N==1:
        print(0)
        return
    odd = set()
    for i in range(N):
        if i&1==0:
            odd.add(A[i])
    A.sort()
    ans = 0
    for i in range((N+1)//2):
        if A[i*2] in odd:
            continue
        ans += 1
    print(ans)
    return

def examD():
    N = I()
    S = [I()for _ in range(N)]

    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Accepted

Solution code:
N, *A = map(int, open(0))
print(len(set(A[1::2]) & set(sorted(A)[::2])))

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline

N, *A = map(int, read().split())
z, _ = zip(*sorted(enumerate(A), key=itemgetter(1)))
z, _ = zip(*sorted(enumerate(z), key=itemgetter(1)))
cnt = 0
for i in range(N):
    if i % 2 != z[i] % 2:
        cnt += 1
print(cnt // 2)

Submission status: Accepted

Solution code:
#C  judge whether its place is even or odd 
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
b = a[::]
b.sort()

dic = dict()
for i,v in enumerate(b):
    dic[v]=i

num = 0    
for i,v in enumerate(a):
    ind = dic[v]
    num += ((i-ind)%2)
print(num//2)

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())
B = sorted(A)
dic = {B[i]:i for i in range(N)}
ans = sum((i+1)%2==dic[n]%2 for i,n in enumerate(A))
print(ans//2)

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())
ans = 0
B = sorted(A)
dic = {B[i]:i for i in range(N)}
for i,n in enumerate(A):
  if i%2!=dic[n]%2:
    ans += 1
print(ans//2)

Submission status: Accepted

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

D = {a:i for i,a in enumerate(sorted(A))}

A = [D[A[i]] for i in range(N)]

count = 0

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

print(count)

Submission status: Accepted

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

D = {a:i for i,a in enumerate(sorted(A))}

A = [D[A[i]] for i in range(N)]

odd = [A[i] for i in range(N) if i%2 == 0]
even = [A[i] for i in range(N) if i%2 == 1]

odd.sort()
even.sort()

B = []

for i in range(N):
    if i%2 == 0:
        B.append(odd[i//2])
    else:
        B.append(even[i//2])

count = 0

for i in range(N):
    if i%2 == 0 and B[i]%2 != 0:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
import numpy as np
lis = np.argsort(np.array(a))

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

Submission status: Accepted

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
odd =[A[i] for i in range(N) if i%2 ==0]
even=[A[i] for i in range(N) if i%2 ==1]
import collections
table=collections.defaultdict(int)
table2=collections.defaultdict(int)
A.sort()
for i in range(N):
  if i %2==0:
    table[A[i]]+=1
for x in odd:
  table2[x]+=1
ans=0

for x in table:
  ans+=(table[x] -table2[x])

print(ans)

Submission status: Accepted

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

b.sort()
cnt = 0
for i in range(n):
    if (i & 1) != (b[i][1] & 1):
        cnt += 1

print(cnt // 2)

Submission status: Accepted

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

def main():
    N =  int(input())
    
    odd,al = [],[]
    for i in range(N):
        a = int(input())
        if i%2 == 0:
            odd.append(a)
        al.append(a)
            
    odd.sort()
    al.sort()
    ans = 0
    for i in range(-(-N//2)):
        num = odd[i]
        index = bisect.bisect_left(al,num)
        if index%2 == 1:
            ans += 1
            
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, *A = map(int, open(0).read().split())
    B = sorted(A)
    S = [set(),set()]
    for i in range(N):
        S[i&1].add(B[i])
    print(sum(a not in S[i&1] for i, a in enumerate(A))//2)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

mp = {}
for i, j in enumerate(A):
	mp[j] = i % 2
	
A.sort()

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

print(ans // 2)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = []
for i in range(n):
    a.append((inn(),i))
a.sort()
cnt = 0
for i in range(0,n,2):
    cnt += a[i][1]%2
print(cnt)

Submission status: Accepted

Solution code:
import copy
from collections import defaultdict
n=int(input())
a=[int(input()) for _ in range(n)]
b=copy.copy(a)
b.sort()
d=defaultdict(int)
for i in range(n):
  d[b[i]]=i
ans=0
for i in range(n):
  if (d[a[i]]-i)%2==1:
    ans+=1
print(ans//2)

Submission status: Accepted

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

n = int(input())
A = map(int, read().split())
L = sorted([(j, i) for i, j in enumerate(A)])
count = 0
for i in range(n):
  count += (L[i][1]-i)%2
print(count//2)

Submission status: Accepted

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

n = int(input())
A = map(int, read().split())
L = sorted([(j, i) for i, j in enumerate(A)])
count = 0
for i in range(n):
  count += (L[i][1]-i)%2
ans = (count+1) // 2
print(ans)

Submission status: Accepted

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

n = int(input())
A = map(int, read().split())
L = sorted([(j, i) for i, j in enumerate(A)])
count = 0
for i in range(n):
  if (L[i][1]-i)%2:
    count += 1
ans = (count+1) // 2
print(ans)

Submission status: Accepted

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

import bisect

B = sorted(A)
ans = 0
for i in range(N):
    idx = bisect.bisect_left(B, A[i])
    if (i-idx)%2 == 1:
        ans += 1

print(ans//2)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])
 
def main():
    n = inp()
    a = []
    for i in range(n):
        a.append((int(input()),i))
    a.sort()
    ans = 0
    for i in range(0,n,2):
        if a[i][1]%2 == 1:
            ans += 1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
N=int(input())
A=[int(input()) for i in range(N)]
sortA=sorted(A)
A0=[]
A1=[]
sortA0=[]
sortA1=[]
for i in range(N):
    if i%2==0:
        A0.append(A[i])
        sortA0.append(sortA[i])
    else:
        A1.append(A[i])
        sortA1.append(sortA[i])

A0=Counter(A0)
A1=Counter(A1)
sortA0=Counter(sortA0)
sortA1=Counter(sortA1)

count0=0
for a in A0:
    if a in sortA0:
        count0+=round(abs(sortA0[a]-A0[a]))
    else:
        count0+=A0[a]
print(count0)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
a = np.array([int(input()) for _ in range(N)])
even_a = a[1::2]
b = np.sort(a)
even_b = b[1::2]
print(len(even_a) - len(set(even_a) & set(even_b)))

Submission status: Accepted

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

oddA = set(A[::2])
oddB = set(B[::2])

ans = len(oddA) - len(oddA & oddB)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def val_arg_tpls_sort(lis):
    val_arg_tpls = (
        (val, i) for i, val in enumerate(lis)
    )
    return list(sorted(val_arg_tpls))


def count_odd_in_even(val_arg_tpls):
    cnt = 0
    for _, arg in val_arg_tpls[::2]:
        cnt += arg % 2
    return cnt


def solve(N: int, A: "List[int]"):
    sorted_tpls = val_arg_tpls_sort(A)
    cnt = count_odd_in_even(sorted_tpls)
    print(cnt)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
N=int(input())
A=[]
for i in range(N):
    A.append([int(input()),i])

As=sorted(A)

cnt=0
for i in range(N):
    if (As[i][1]-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()), i) for i in range(N)]
A_sorted = sorted(A)
count = 0
for i in range(N):
    count += (A_sorted[i][1] - i) % 2
print(count // 2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, A: "List[int]"):

    # Aを0~N-1に付け直す
    dic = {}
    for i, a in enumerate(sorted(A)):
        dic[a] = i
    B = [dic[a] for a in A]

    # Bの内、偶数番目にある奇数の数だけ操作1が必要
    count = 0
    for i in range(0, N, 2):
        if B[i] % 2 == 1:
            count += 1
    print(count)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list({int(input()):i for i in range(N)}.items()),key=lambda x:x[0])
cnt = 0
for i in range(N):
    j = A[i][1]
    if i%2!=j%2:
        cnt += 1
print(cnt//2)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A)
D = {b: i for i, b in enumerate(B)}

ans = 0
for i, a in enumerate(A):
    if (i ^ D[a]) % 2:
        ans += 1
print(ans // 2)

Submission status: Accepted

Solution code:
n=int(input())
a = [(i,int(input())) for i in range(n)]
a.sort(key=lambda x:x[1])
cnt = 0
for i,tup in enumerate(a):
  x=tup[0]
  if (x-i)%2:
    cnt += 1
print(cnt//2)

Submission status: Accepted

Solution code:
n = int(input())
A = [int(input()) for i in range(n)]
B = A[:]

D = {}
A.sort()
for i in range(n):
    D[A[i]] = i

for i in range(n):
    B[i] = D[B[i]]

# print(B)
ans = 0
for i in range(n):
    if i % 2 != B[i] % 2:
        ans += 1
print((ans+1) // 2)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = [int(input()) for _ in range(N)]
B = A[:]
B.sort()
idx = defaultdict(int)

for i in range(N):
    idx[B[i]] = i

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(a[::2])
a.sort()
now = 0
ans = 0
br = len(b)
for k,v in enumerate(a):
  if b[now] == v:
    if k % 2:
      ans += 1
    now += 1
  if now == br:
    break
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=[[0]*2 for i in range(n)]
for i in range(n):
  A[i][0]=int(input())
  A[i][1]=i%2
A.sort(key=lambda x:x[0])
ans=0
for i in range(n):
  if i%2==0:
    ans=ans+A[i][1]
print(ans)

Submission status: Accepted

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

N = int(input())

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

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

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

print (count // 2)

Submission status: Accepted

Solution code:
import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [ri() for _ in range(N)]
x_to_i = {x:i for i, x in enumerate(sorted(A))}
rank = [x_to_i[x] for x in A]
answer = sum((i^x)&1 for i,x in enumerate(rank)) // 2
print(answer)

Submission status: Accepted

Solution code:
import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [ri() for _ in range(N)]
x_to_i = {x:i for i, x in enumerate(sorted(A))}
rank = [x_to_i[x] for x in A]
answer = sum(i&1 and (i^x)&1 for i,x in enumerate(rank))
print(answer)

Submission status: Accepted

Solution code:
import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [ri() for _ in range(N)]
B = sorted(A)
B = set(B[1::2])
C = [i%2==1 and a not in B for i, a in enumerate(A)]
print(sum(C))

Submission status: Accepted

Solution code:
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [ri() for _ in range(N)]
B = sorted(A)
B = set(B[1::2])
C = [i%2==1 and a not in B for i, a in enumerate(A)]
print(sum(C))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・偶数番号、奇数番号の中では入れ替え放題
・偶、奇の間：並べてからスワップ。操作2を1回で、正しいものを2つ増やせる
"""

N,*A = map(int,read().split())

x_to_i = {x:i for i,x in enumerate(sorted(A))}
rank = [x_to_i[x] for x in A]

answer = sum((x^i) & 1 for i,x in enumerate(rank)) // 2
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(a[::2])
a.sort()
now = 0
ans = 0
br = len(b)
for k,v in enumerate(a):
  if b[now] == v:
    if k % 2:
      ans += 1
    now += 1
  if now == br:
    break
print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
A = list(int(input())for i in range(N))
ans = 0
B = sorted(A)
for i in range(N):
    if i%2 != bisect.bisect_left(B, A[i])%2:
        ans += 1
print(ans//2)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

#インデックス付きソート
#(index,value)の順に格納
from operator import itemgetter
def index_sort(A):
    return sorted(enumerate(A),key=itemgetter(1))

N = I()
A = Line(N,1)

B = index_sort(A)
num = 0
for i in range(N):
    if abs(B[i][0]-i)%2==1:
        num += 1

print(num//2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=[(int(input()),i) for i in range(n)]
    A.sort()
    d=0
    for i,tup in enumerate(A):
        a,j=tup
        d+=abs(j-i)%2

    print(d//2)
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def examC():
    N = I(); A = [I() for _ in range(N)]
    AS = sorted(A)
    A0 = A[::2]
    d = defaultdict(bool)
    for i in AS[::2]:
        d[i] = True
    ans = 0
    for i in A0:
        if not d[i]:
            ans +=1
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Submission status: Accepted

Solution code:
from collections import namedtuple
from operator import attrgetter

Number = namedtuple('Number', 'number idx')

n = int(input())

a = []
for idx in range(n):
    k = int(input())
    a.append(Number(number=k, idx=idx))

a.sort(key=attrgetter('number'))

ret = 0
for j, a_ in enumerate(a):
    if (j - a_.idx) % 2 != 0:
        ret += 1
print(ret // 2)

Submission status: Accepted

Solution code:
N = int(input())

A = []

for i in range(N):

    a = int(input())
    A.append([a,i % 2])

A.sort()
ans = 0

for i in range(N):

    if i % 2 != A[i][1]:
        ans += 1

print (ans // 2)

Submission status: Accepted

Solution code:
print(sum([abs(k-j)%2 for k,[i,j] in enumerate(sorted([[int(input()),i] for i in range(int(input()))]))])//2)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    a=[int(input()) for _ in [0]*n]
    a=sorted([[a[i],i] for i in range(n)])
    for i in range(n):
        a[i][0]=abs(i-a[i][1])%2
    a=[i[0] for i in a]
    print(sum(a)//2)
main()

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = []
	for i in range(N):
		a = int(input())
		A.append([a, i])
	B = sorted(A)
	ans = 0
	for i in range(N):
		if A[i][1] % 2 == 1 and B[i][1] % 2 == 0:
			ans += 1
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


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

A = np.array(A, dtype=int)

a = set(A[::2])
b = set(np.msort(A)[::2])

ans = len(a - b)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, A):
    A_ = [(a, i%2) for i, a in enumerate(A)]
    A_.sort()

    ans = 0
    for i, (_, j) in enumerate(A_):
        if i % 2 != j:
            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:
from bisect import bisect_left

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

B = sorted(A)

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

Submission status: Accepted

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
S=sorted(A)
from bisect import bisect_left
p=[0]*N
for i,a in enumerate(A):
    p[bisect_left(S,a)]=i
print(sum([(p[i]-i)%2 for i in range(N)])//2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N = int(input())
a = []
d = dict()
res = 0
for i in range(N):
  a.append(int(input()))
  d[a[i]] = i
b = sorted(a)
for i in range(N):
  j = d[b[i]]
  res += abs(i - j) % 2
print(res // 2)