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())
a = []
for i in range(n):
  x = int(input())
  a.append(x)
zi = {}
b= sorted(a)
for i in range(n):
  zi[b[i]] = i
g = 0
k = 0
for i in range(n):
  if zi[a[i]] %2 == i%2:
    continue
  elif i%2 == 1:
    g += 1
  else:
    k += 1
print(g)

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc 003
"""

from operator import itemgetter

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

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

print(ansdouble//2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

a = []

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

print(ans//2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding:utf-8

INF = float('inf')


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


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

print(N - len(D))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

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

from bisect import bisect_left

dic = dict()

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(ass//2)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

As.sort()

# ソート後の位置が偶数である要素のうち、元の位置が奇数であるものの個数が答え
print(len([A for A, i in As[::2] if i % 2]))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from copy import deepcopy
N = int(input())
A = [int(input()) for i in range(N)]

B = deepcopy(A)
B.sort()
odd, even = set(), set()
for i in range(N):
    if i % 2 == 0:
        even.add(B[i])
    else:
        odd.add(B[i])

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

print(ans // 2)

Submission status: Accepted

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

for i in range(n):
    if abs (i - nums[i][1]) % 2 == 1:
        ans += 1

print(ans // 2)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


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


B = sorted(A)
d = {}


for i in range(N):
    d[A[i]] = i % 2

count = 0
for i in range(N):
    # d[B[i]] = (d[B[i]] + i) % 2
    count += (d[B[i]] + i) % 2


print(count//2)

Submission status: Accepted

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

sortedA = sorted(A)
dic = {}
for i in range(N):
    dic[sortedA[i]] = i

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

Submission status: Accepted

Solution code:
n = int(input())
nums = []
evens = set()
for i in range(n):
  tmp = int(input())
  nums.append(tmp)
  if i%2==0:
    evens.add(tmp)
nums.sort()
count = 0
for j in range(n):
  if j%2 == 0:
    if nums[j] not in evens:
      count += 1
print(count)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
  a=int(input())
  A.append(a)
res=sorted(A)

def binary_search(x):
  l=0
  r=N-1

  while True:
    mid=(l+r)//2
    if res[mid]==x:
      return mid
    elif res[mid]>x:
      r=mid-1
    elif res[mid]<x:
      l=mid+1

ans=0
for j,k in enumerate(A):
  cnt=binary_search(k)
  if abs(j-cnt)%2==1:
    ans+=1

print(ans//2)

Submission status: Accepted

Solution code:


n = input()
elems = []
for _ in range(n):
    elems.append(input())

inds = range(n)
inds.sort(key=lambda x: elems[x])

resp = 0
for i in range(n):
    if (inds[i] + i) % 2:
        resp += 1

print(resp / 2)

Submission status: Accepted

Solution code:
def minimumOpt1(seq):
    dest = {}
    b = sorted(seq)
    for i in xrange(len(b)):
        dest[b[i]] = i
    foo = 0
    for i in xrange(0, len(seq), 2):
        if dest[seq[i]]%2==1:
            foo += 1
    return foo

def main():
    n = int(raw_input().strip())
    seq = [0] * n
    for i in xrange(n):
        seq[i] = int(raw_input().strip())
    print minimumOpt1(seq)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def minimumOpt1(seq):
    dest = {}
    b = sorted(seq)
    for i in xrange(len(b)):
        dest[b[i]] = i
    foo = 0
    for i in xrange(0, len(seq), 2):
        if dest[seq[i]]%2==1:
            foo += 1
    return foo

def main():
    n = int(raw_input().strip())
    seq = []
    for i in xrange(n):
        seq.append(int(raw_input().strip()))
    print minimumOpt1(seq)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import math
N = int(input())
s = [int(input()) for _ in range(N)]
sn=np.array(s)
sa=sn.argsort()
x=0
for i in range(N):
  if i %2 != sa[i] %2:
    x+=1
print(math.ceil(x/2))

Submission status: Accepted

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

odd = 0
for new_order, (a, old_order) in enumerate(src):
    if (new_order - old_order) % 2:
        odd += 1
print(odd // 2)

Submission status: Accepted

Solution code:
n = int(input())
ls = []
for i in xrange(0, n):
    ls.append(int(input()))
sls = sorted(ls)
st = {j for i, j in enumerate(ls) if i % 2 == 1}
sst = {j for i, j in enumerate(sls) if i % 2 == 1}
print(len(st.difference(sst)))

Submission status: Accepted

Solution code:
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####

def main():
	N=I()
	A=ALL_IL()
	B=sorted(A.copy())

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

	print(len(a-b))


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N = int(input())
    A_list = list(sorted([(int(input()), i) for i in range(N)]))
    a_list = [i for a, i in A_list]
    ans = 0
    for i, a in enumerate(a_list):
        ans += (i % 2 != a % 2)
    print(ceil(ans, 2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin

def binarysearch(cadena,x):
	low,hi = 0,len(cadena)
	while low+1 != hi:
		mid = low +((hi - low)//2)
		if x < cadena[mid]:
			hi = mid
		else:
			low = mid
	return low

def main():
	N = int(stdin.readline().strip())
	i,number,copy = 0,[-1 for x in range(N)],[-1 for x in range(N)]
	while i < N:
		x = int(stdin.readline().strip())
		number[i] = x
		copy[i] = x
		i+=1
	i,op1 = 0,0
	copy.sort()
	while i < N:
		pos = binarysearch(copy,number[i])
		if (abs(pos-i))%2!= 0:
			op1+=1
		i+=1
	ans = op1//2
	print(ans)
main()

Submission status: Accepted

Solution code:
n = int(raw_input())
ls = [int(raw_input()) for _ in range(n)]
sls = sorted(ls)
st = {j for i,j in enumerate(ls) if i % 2 == 1}
sst = {j for i,j in enumerate(sls) if i % 2 == 1}
print len(st.difference(sst))

Submission status: Accepted

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

###########

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


print cnt/2

Submission status: Accepted

Solution code:
import sys

#sys.stdin = open('input2.txt', 'r')

N = int(raw_input())
seq = []
for x in range(N):
	a = long(raw_input())
	seq.append((a, x))
seq.sort()

count = 0
for x in range(N):
	a, i = seq[x][0], seq[x][1]
	if ((x - i) % 2):
		count += 1

print str(count / 2)

Submission status: Accepted

Solution code:
import numpy as np

N = int(raw_input())
A = [0] * N
for idx in xrange(N):
  A[idx] = int(raw_input())
A = np.array(zip(A,range(N)))
B = np.array(sorted(A, key=lambda x:x[0]))
C = np.array([x[1] for x in B])
D = np.array(range(N))
C = C % 2
D = D % 2
E = np.abs(C - D)

print sum(E)/2

Submission status: Accepted

Solution code:
def solve(a):
	l = len(a)
	h = l//2 + l%2
	a0 = [a[2*i] for i in range(h)]
	b = a.copy()
	b.sort()
	b0 = [b[2*i] for i in range(h)]

	a0 = set(a0)
	b0 = set(b0)

	return len(a0 - b0)
n = int(input())
a = [int(input()) for i in range(n)]
print(solve(a))

Submission status: Accepted

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

ans = 0

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

print(ans)

Submission status: Accepted

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

even_num = set((a[i] for i in range(0,n) if i % 2 == 0))

a.sort()

odd_num = set((a[i] for i in range(0, n) if i % 2 == 1))

count = len(even_num & odd_num)
print(count)

Submission status: Accepted

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

even_num = set([a[i] for i in range(0,n) if i % 2 == 0])

a.sort()

odd_num = set([a[i] for i in range(0, n) if i % 2 == 1])

count = len(even_num & odd_num)
print(count)

Submission status: Accepted

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

even_num = set([a[i] for i in range(0,n) if i % 2 == 0])

a = sorted(a)

odd_num = set([a[i] for i in range(0, n) if i % 2 == 1])

count = len(even_num & odd_num)
print(count)

Submission status: Accepted

Solution code:
N = input()
a = sorted([(int(raw_input()), i) for i in xrange(N)])
print sum([i%2 != j[1]%2 for i, j in enumerate(a)]) / 2

Submission status: Accepted

Solution code:
n=int(input())
arr=[]
dic={}
for i in range(0,n):
    a = int(input())
    arr.append(a)
    dic[a]=i%2
#print(dic)
brr=sorted(arr)
diff=0
for i in range(0,n):
    if dic[brr[i]] != i%2:
        diff+=1
print(diff//2)

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    e = [a[i] for i in range(0, n, 2)]
    a.sort()
    o = set(a[i] for i in range(1, n, 2))
    ans = 0
    for i in range((n + 1) // 2):
        if e[i] in o:
            ans += 1
    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N = int(raw_input())
A = [int(raw_input()) for i in xrange(N)]

B = sorted(A)
X = set([A[i] for i in xrange(N) if i%2 == 0])
Y = set([B[i] for i in xrange(N) if i%2 == 0])

print len(Y - X)

Submission status: Accepted

Solution code:
from sys import stdin

n=int(input())
valeurs=[0]*n
minimum=0
for i in range(n):
    valeur=int(stdin.readline())
    valeurs[i]=[valeur,i]
valeurs.sort()
compteur=[0]*2
for i in range(n):
    indice=valeurs[i][1]
    if i%2!=indice%2:
        compteur[indice%2]+=1
print(max(compteur))

Submission status: Accepted

Solution code:
n = input()
A = [int(raw_input()) for i in xrange(n)]
B = A[0:n:2]
C = A[1:n:2]
A.sort()
B.sort()
C.sort()
ans = 0
idxB = 0
idxC = 0
for i in xrange(n):
    if i%2:
        if idxB < len(B) and B[idxB] == A[i]:
            ans += 1
    else:
        if idxC < len(C) and C[idxC] == A[i]:
            ans += 1
    if idxB < len(B) and B[idxB] == A[i]:
        idxB += 1
    if idxC < len(C) and C[idxC] == A[i]:
        idxC += 1
print ans/2

Submission status: Accepted

Solution code:
n = input()
a = []
b = []
l = []
for _ in xrange(n):
    t = input()
    if _%2 == 0:
        a.append(t)
    else:
        b.append(t)
    l.append(t)
a = sorted(a)
b = sorted(b)
l = sorted(l)
c = 0
i = 0
for k,m in enumerate(l):
    if i < len(a) and m == a[i]:
        i += 1
        if k%2 == 1:
            c += 1
    else:
        if k%2 == 0:
            c += 1
print c/2

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline())
a = [int(stdin.readline()) for _ in xrange(n)]
b = [a[0::2], a[1::2]]
ans = t = 0
a.sort()
d = dict()
for x in a:
    d[x] = t
    t = 1 - t
for i, l in enumerate(b):
    for x in l:
        ans += d[x] ^ i
print ans / 2

Submission status: Accepted

Solution code:
N = int(input())
a = [int(input())  for i in range(N)]
index = sorted(range(len(a)), key=lambda k: a[k])
count = 0
for i in range(N):
    if (index[i]+i)%2 ==1:
        count = count + 1
print('%s' % str(count//2))

Submission status: Accepted

Solution code:
n = input()
l1 = []

for i in range(n):
	t = input()
	l1.append(t)

l2 = sorted(l1)

s1, s2 = set([]), set([])

for i in range(n):
	if i % 2 == 1:
		s1.add(l1[i])
		s2.add(l2[i])

print len(s1) - len(s1.intersection(s2))

Submission status: Accepted

Solution code:
N = int(input())
xs = list(map(int, (input() for _ in range(N))))
ss = sorted(xs)
odd1 = set((x for i, x in enumerate(xs) if i % 2 == 1))
even2 = set((s for i, s in enumerate(ss) if i % 2 == 0))
print(len(odd1 & even2))

Submission status: Accepted

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

N = int(input())
nums = [0] * N
for pos in range(N):
    nums[pos] = int(input())
snums = sorted(nums[:])
rank = {}
for i,e in enumerate(snums):
    rank[e] = i+1

rev = 0
for i,e in enumerate(nums):
    if (i + rank[e]) % 2 == 0:
        rev += 1
print(rev // 2)

Submission status: Accepted

Solution code:
n = int(raw_input())
values = [ int(raw_input()) for i in range(n) ]
place = { x: i for i, x in enumerate(sorted(values)) }
count = 0
for i, x in enumerate(values):
    if i % 2 != place[x] % 2:
        count += 1
result = count // 2 + count % 2
print(result)

Submission status: Accepted

Solution code:
n = int(input())
A = [0]*n

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

SO = A[:]
SO.sort()

##
def check(mid, now):
	return now >= SO[mid]


def binarySearch(small, big, now):
	mid = (big + small) // 2
	if big == small or big == small + 1:
		if SO[big] == now:
			return big
		else:
			return small
	else:
		if check(mid, now):
			return binarySearch(mid, big, now)
		else:
			return binarySearch(small, mid, now)


##
ans = 0
for i in range(n):
	now = A[i]
	gi = binarySearch(0, n-1, now)
	if i % 2 != gi % 2:
		ans += 1


print(ans // 2)

Submission status: Accepted

Solution code:
import bisect
n=int(raw_input())
a=[int(raw_input()) for _ in xrange(n)]
cnt=0
sa=sorted(a)
for i in xrange(n):
    if abs(i-bisect.bisect_left(sa,a[i]))%2!=0:
        cnt+=1
print(cnt/2)

Submission status: Accepted

Solution code:
import operator

N = int(raw_input())

A = [int(raw_input())-1 for i in range(N)]

Dindices = [i for (i,a) in sorted(enumerate(A), key=operator.itemgetter(1))]

print sum(1 for (i,Di) in enumerate(Dindices) if (Di-i)%2 == 1) // 2

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
sorted_A = sorted(A)
d = {}
for i in range(N):
    d[sorted_A[i]] = i
# print(d)
cnt = 0
for i in range(N):
    if i % 2 == 0 and d[A[i]] % 2 != 0:
        cnt += 1
    elif i % 2 != 0 and d[A[i]] % 2 == 0:
        cnt += 1
ans = cnt // 2
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

N = n()


pos = {}

A = []
for i in xrange(N):
    a = n()
    A.append(a)
    pos[a] = i

A.sort()

c = 0
ok = True
for i in xrange(N):
    if pos[A[i]] % 2 != i % 2:
        c += 1

print c / 2

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**9

n = int(input())
a = [[int(input()),_] for _ in range(n)]
a.sort()
r = 0
for i in range(0,n,2):
    if a[i][1] % 2 == 1:
        r += 1
print(r)

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(0,N,2):
    if A[i][1] % 2 == 1:
        Ans += 1
print(Ans)

Submission status: Runtime Error

Solution code:
class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.k_init = 2 ** (self.n - 1).bit_length()

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i


def get_invnum(li):
    n = len(li)
    t = FenwickTree(max(li))
    res = 0
    for i in range(n):
        res += i - t.sum(li[i])
        t.add(li[i], 1)
    return res


N, *A = map(int, open(0).read().split())
triplet_sorted_A = [0] * N
triplet_sorted_A[::2] = sorted(A[::2])
triplet_sorted_A[1::2] = sorted(A[1::2])
print(get_invnum(triplet_sorted_A))

Submission status: Runtime Error

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

Submission status: Runtime Error

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: Runtime Error

Solution code:
n=int(input())
a=[int(input()) for i in range(n)]
b=a[::2]
c=a[1::2]
b.sort()
c.sort()
a=[c[i] if i&1 else b[i] for i in range(n)]
cnt=0
for i in range(n-1):
	if a[i]>a[i+1]:
		cnt+=1
		a[i],a[i+1]=a[i+1],a[i]
print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[int(input() for i in range(n)]
b=a[::2]
c=a[1::2]
b.sort()
c.sort()
a=[c[i] if i&1 else b[i] for i in range(n)]
cnt=0
for i in range(n-1):
	if a[i]>a[i+1]:
		cnt+=1
		a[i],a[i+1]=a[i+1],a[i]
print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())

ans=0

a=[]
b=[]

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

cnt=0
for i,v in enumerate(a):
    if i%2 != (b.index(v))%2:
        cnt+=1
print(cnt//2)

Submission status: Runtime Error

Solution code:
n=int(input())

ans=0

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

b=a.sorted()

cnt=0
for i,v in enumerate(a):
    if i%2 != (b.index(b))%2:
        cnt+=1
print(cnt//2)

Submission status: Runtime Error

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

a=A.copy()
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: Runtime Error

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: Runtime Error

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

Submission status: Runtime Error

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(np.array(A))
C = [np.where(B == a)[0][0] for a in A]
answer = sum([i%2==1 and x%2!=1 for i, x in enumerate(C)])
print(answer)
# 41

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    a=[]
    b=[]
    if n == 1:
        a=int(input())
        print(0)
    else:
        for i in range(n//2):
            a.append(int(input()))
            b.append(int(input()))

        if n % 2 == 1:
            a.append(int(input()))

        a.sort()
        b.sort()
        ta=a[0]
        tb=b[0]
        if ta < tb:
            res = 0
        else:
            tb = ta
            res = 1

        for i in range(1,n//2+1):
            if a[i] < tb:
                ta = tb
                res += 1
            else:
                ta = a[i]
            if b[i] < ta:
                tb =ta
                res += 1
            else:
                tb = b[i]
        if n % 2 == 1:
            if a[-1] < tb:
                res += 1

        print(res)
main()

Submission status: Runtime Error

Solution code:
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(N, 2):
    a, j = A[i]
    cnt += j & 1
print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input()) + 1

A_even = A[::2]
A_odd = A[1::2]
A_even = sorted(A_even)
A_odd = sorted(A_odd)
A_sorted = [0] * N
for i in range(N):
    if i % 2 == 0:
        A_sorted[i] = A_even[i // 2]
    else:
        A_sorted[i] = A_odd[i // 2]


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, idx):
        s = 0
        while idx > 0:
            s += self.tree[idx]
            idx -= idx & -idx
        return s

    def add(self, idx, x):
        while idx <= self.size:
            self.tree[idx] += x
            idx += idx & -idx


bit = Bit(max(A) + 1)
ans = 0
for i in range(N):
    bit.add(A_sorted[i], 1)
    ans += i + 1 - bit.sum(A_sorted[i])

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input()) + 1

A_even = A[::2]
A_odd = A[1::2]
A_even = sorted(A_even)
A_odd = sorted(A_odd)
A_sorted = [0] * N
for i in range(N):
    if i % 2 == 0:
        A_sorted[i] = A_even[i // 2]
    else:
        A_sorted[i] = A_odd[i // 2]


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, idx):
        s = 0
        while idx > 0:
            s += self.tree[idx]
            idx -= idx & -idx
        return s

    def add(self, idx, x):
        while idx <= self.size:
            self.tree[idx] += x
            idx += idx & -idx


bit = Bit(max(A))
ans = 0
for i in range(N):
    bit.add(A_sorted[i], 1)
    ans += i + 1 - bit.sum(A_sorted[i])

print(ans)