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: Wrong Answer

Solution code:
import bisect

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

N = int(input())
a = []
b = []

for i in range(N):
	A = int(input())
	if i % 2 == 0:
		a.append(A)
	else:
		b.append(A)

a = sorted(a)
b = sorted(b)
x = len(a)
y = len(b)
ans = 0
for i in range(len(b)):
	ans += abs(bisect.bisect_left(a, b[i]) - i - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

N = int(input())
a = []
b = []

for i in range(N):
	A = int(input())
	if i % 2 == 0:
		a.append(A)
	else:
		b.append(A)

a = sorted(a)
b = sorted(b)
ans = 0
for i in range(len(b)):
	ans += abs(bisect.bisect_left(a, b[i]) - i - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
def getlist():
	return list(map(int, input().split()))

N = int(input())
a = []
b = []

for i in range(N):
	A = int(input())
	if i % 2 == 0:
		a.append(A)
	else:
		b.append(A)

a = sorted(a)
b = sorted(b)

C = []
for i in range(N):
	if i % 2 == 0:
		C.append(a[i // 2])
	else:
		C.append(b[i // 2])

ans = 0
for i in range(N - 1):
	if C[i] > C[i + 1]:
		ans += 1
		C[i + 1], C[i] = C[i], C[i + 1]

print(ans)

Submission status: Wrong Answer

Solution code:
def getlist():
	return list(map(int, input().split()))

N = int(input())
a = []
b = []

for i in range(N):
	A = int(input())
	if i % 2 == 0:
		a.append(A)
	else:
		b.append(A)

a = sorted(a)
b = sorted(b)

C = []
for i in range(N):
	if i % 2 == 0:
		C.append(a[i // 2])
	else:
		C.append(b[i // 2])

ans = 0
for i in range(N // 2):
	if C[2 * i + 1] < C[2 * i]:
		ans += 1

print(ans)

Submission status: Wrong Answer

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 = 0
i = 0
while i < m - 1:
    if lst[i] + 1 == lst[i+1]:
        ans += 1
        i += 2
    else:
        ans += 1
        i += 1
print(ans)

Submission status: Wrong Answer

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>1:
  ans-=1
  
print(ans)

Submission status: Wrong Answer

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 + 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: Wrong Answer

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 d1, d2 in zip(d, d_s):
    if d1 == d2:
        continue
    else:
        cnt += 1
print(cnt//2)

Submission status: Wrong Answer

Solution code:
def sort_with_three(a):
    changed = True
    while True:
        if not changed:
            break
        changed = False
        for i in range(1, N+1-2):
            if a[i] > a[i+2]:
                a[i], a[i+2] = a[i+2], a[i]
                changed = True
    return a

def sort_once(a):
    for i in range(1, N):
        if a[i] > a[i+1]:
            a[i], a[i+1] = a[i+1], a[i]
            break
    return a

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

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

sorted_A = sorted(A)

ans = 0
while True:
    A = sort_with_three(A)
    if A == sorted_A:
        break
    if ans > 9:
        break
    ans += 1
    A = sort_once(A)

print(ans)

Submission status: Wrong Answer

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-1)
#print(a)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
    if i % 2:
        b.append(int(input()))
    else:
        a.append(int(input()))
a.sort()
b.sort()
c = a + b
c.sort()
ans = 0
for i in range(n-1):
    if i%2 == 0:
        if a[i//2] == c[i]:
            continue
        else:
            ans += 1
            b[i//2] = a[i//2]
    else:
        if b[i//2] == c[i]:
            continue
        else:
            ans += 1
            a[i//2+1] = b[i//2]
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
s = int(input())
a = []
count = 0
for j in range(s):
        a.append(input())
b = sorted(a)
for i in range(s):
    if  (i + b.index(a[i]))%2 == 1:
            count += 1
count = count//2 + count%2
print(count)

Submission status: Wrong Answer

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
for a in A:
	if C.index(a)%2==1:
		c+=1
for b in B:
	if C.index(b)%2==0:
		c+=1
print(c)

Submission status: Wrong Answer

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=sorted(a[::2])
    c=sorted(a[1::2])
#    print(b,c)
    ans=0
    for i in range(n//2):
        ans+=abs(i-bisect_left(c,b[i]))
#        print(b[i],i,bisect_left(c,b[i]))
    if len(b)!=n//2:
        ans+=abs(n//2-bisect_left(c,b[-1]))
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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=sorted(a[::2])
    c=sorted(a[1::2])
#    print(b,c)
    ans=0
    for i in range(n//2):
        ans+=abs(i-bisect_left(c,b[i]))
#        print(b[i],i,bisect_left(c,b[i]))
    if len(b)!=n//2:
        ans+=n//2-bisect_left(c,b[-1])
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [int(input()) for _ in range(n)]
cnt =  0
for i in range(0,n,2):
  if l[i]%2==0:
    cnt += 1
print(cnt)

Submission status: Wrong Answer

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

class BIT:
    def __init__(self, N):
        self.size = 2 ** (int.bit_length(N)+1)
        self.tree = [0]*(self.size + 1)
 
    def sum(self, i):
        res = 0
        while i:
            res += self.tree[i]
            i -= (i & -(i))
        return res
 
    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.tree[i] += x
            i += (i & -(i))


N = int(input())
A = [0] + [int(input()) for _ in range(N)]
B = list(range(1, N+1))
B = sorted(B, key=lambda x: -A[x])
B1 = sorted(B[::2])
B2 = sorted(B[1::2])
for i in range(0, N, 2):
    B[i] = B1[i//2]
for i in range(1, N, 2):
    B[i] = B2[i//2]

bitree = BIT(N)

ans = 0
for j in range(N):
    ans += j - bitree.sum(B[j])
    bit = bitree.add(B[j], 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = list(enumerate([int(input()) for _ in range(N)]))
B = [iv[0]+1 for iv in sorted(
    enumerate([i for i, v in sorted(A, key=lambda xs: xs[1])]),
    key=lambda xs: xs[1])]
C = list(
    itertools.chain.from_iterable(
        itertools.zip_longest(sorted(B[::2]), sorted(B[1::2]))))
if C[-1] == None:
    C = C[:-1]


class SegmentTree():
    """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        e : 
            identity element of the monoid
        size : int
            limit for array size
    """

    def __init__(self, array, f, e, size):
        self.f = f
        self.e = e
        self.size = size
        self.n = n = len(array)
        self.dat = [e] * n + array + [e] * (2 * size - 2 * n)
        self.build()

    def build(self):
        dat, n, f = self.dat, self.n, self.f
        for i in range(n - 1, 0, -1):
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def modify(self, p, v):
        """
        set value at position p (0-indexed)
        """
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            dat[p >> 1] = f(dat[p], dat[p ^ 1])
            p >>= 1

    def query(self, l, r):
        """
        result on interval [l, r) (0-indexed)
        """
        f, e, n, dat = self.f, self.e, self.n, self.dat
        res = e
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(res, dat[r])
            l >>= 1
            r >>= 1
        return res


e = 0
size = N + 1
ST = SegmentTree([0] * N, f=lambda x, y: x + y, e=e, size=size)
ans = N * (N + 1) // 2
for c in C:
    ST.modify(c, ST.query(c, c + 1) + 1)
    ans -= ST.query(1, c + 1)
print(ans)

Submission status: Wrong Answer

Solution code:
print(sum([1 for j in [int(input()) for i in range(int(input()))][::2] if j%2!=0]))

Submission status: Wrong Answer

Solution code:
print(sum([1 for j in [int(input()) for i in range(int(input()))][::2] if j%2!=1]))

Submission status: Wrong Answer

Solution code:
print(len([i for i in [i for i in range(int(input()))][::2] if i%2!=0]))

Submission status: Wrong Answer

Solution code:
print(len([i for i in [i for i in range(int(input()))][::2] if i%2!=1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
b = sorted(a)
aa = []
bb = []
for i in range(0,n,2):
    aa.append(a[i])
    bb.append(b[i])
aa.sort()
cnt = 0
for i in range(n//2):
    if aa[i] != bb[i]:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

count=0
i=0
j=0
while i<len(A) and j<len(B):
    if i<=j:
        if A[i]>B[j]:
            count+=j-i+1
            j+=1
        else:
            i+=1
    else:
        if A[i]<B[j]:
            count+=i-j
            i+=1
        else:
            j+=1

print(count)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
import math
n = int(input())
a = [int(input()) for _ in range(n)]
kaisuu = 0
for j in range(int(math.log(n)+1)):
 for i in range(n-2):
   if a[i]>a[i+2]:
    a[i],a[i+2] = a[i+2],a[i]
for k in range(int(math.log(n)+1)):
  for i in range(n-1):
    if a[i]>a[i+1]:
      kaisuu+=1
      a[i],a[i+1] = a[i+1],a[i]
print(kaisuu)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
N=int(input())
A=[]
B=[]
for i in range(N):
    s=int(input())
    if i%2==0:
        A.append(s)
    else:
        B.append(s)
A.sort()
B.sort()
ans=0
for i in range(len(B)):
    s=bisect(A,B[i])
    ans+=abs(s-i-1)
    #print(ans,':',s,i)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

O = []
E = []
i = 0

while i < N:
  if i%2 == 1:
    E.append(int(input()))
  else:
    O.append(int(input()))
  i += 1
  
O.sort()
E.sort()

ans = 0
io, ie = 0, 0
while io < len(O) and ie < len(E):
  #print(O[io], E[ie])
  if O[io] < E[ie]:
    pass
  else:
    ans += 1
    O[io], E[ie] = E[ie], O[io]
    
  io += 1
  if io >= len(O):
    break
  #print(E[ie], O[io])

  if O[io] > E[ie]:
    pass
  else:
    ans += 1
    O[io], E[ie] = E[ie], O[io]
  
  ie += 1
  
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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][0],X[0][1],X[1][0],X[1][1]]
print(min(Y))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(input()) for _ in range(N)]
even=sorted(A[::2])
odd=sorted(A[1::2])
i,j,ans = 0,0,0
for c in range(N):
    if(len(odd)==j or (len(even)>i and even[i]<odd[j])):
        ans += abs(c-(i*2))
        i += 1
    else:
        ans += abs(c-(j*2+1))
        j += 1
print(ans//2)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
nums,odds,evens = [],[],[]
for i in range(n):
  tmp = int(input())
  nums.append(tmp)
  if i%2==0:
    evens.append(tmp)
  else:
    odds.append(tmp)
nums.sort()
odds.sort()
evens.sort()
count = 0
for j in range(n):
  if j%2 == 0:
    if nums[j] != evens[j//2]:
      count += 1
  else:
    if nums[j] != odds[j//2]:
      count += 1
print(count//2)

Submission status: Wrong Answer

Solution code:
N = int(input())

evens = []
odds = []
for i in range(N):
    a = int(input())
    if i % 2 == 0:
        evens.append(a)
    else:
        odds.append(a)

evens.sort()
odds.sort()

c = 0
for even, odd in zip(evens, odds):
    if odd < even:
        c += 1

print(c)

Submission status: Wrong Answer

Solution code:
N=int(input())
l=[int(input()) for _ in range(N)]
cnt=0
if(N<3):
    if N==1:print("0")
    elif l[0]>l[1]:print("1")
    else:print("0")
for _ in range(N):
    for i in range(N-2):
        if l[i]>l[i+2]:
            l[i], l[i + 2] = l[i + 2], l[i]
for _ in range(N):
    for i in range(N-1):
        if(l[i]>l[i+1]):
            l[i],l[i+1]=l[i+1],l[i]
            cnt+=1
print(cnt)

Submission status: Wrong Answer

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

	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: Wrong Answer

Solution code:
#coding: cp932
N = int(input())
inp =[]
for s in range(N):
	inp.append(int(input()))

flag=1
s,ans,lis2 = 0,0,[]

while flag==1:
	lis2.append(inp[s])
	s+=2
	if s>N-1:
		flag=0
inp.sort()
num =len(lis2)

for s in range(num):
	if (s+1)%2!=1:	continue
	if s!=0:
		if inp[s+1] not in lis2:
			ans+=1
		continue
	elif s==0:
		if inp[s] not in lis2:
			ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#C
n = int(input())
a = []
cnt = [0] * 100001
for i in range(n):
    ai = int(input())
    a.append(ai)

    if i % 2 == 0:
        cnt[a[i]] += 1

a.sort()

cnt2 = [0] * 100001
for i in range(n):
    if i % 2 == 0:
        cnt2[a[i]] += 1

ans = 0
for i in range(n):
    ans += abs(cnt2[i] - cnt[i])

print(ans)

Submission status: Wrong Answer

Solution code:
#C
n = int(input())
a = []
cnt = [0] * n
for i in range(n):
    ai = int(input())
    a.append(ai)

    if i % 2 == 0:
        cnt[i] += 1

a.sort()

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

ans = 0
for i in range(n):
    ans += abs(cnt2[i] - cnt[i])

print(ans)

Submission status: Wrong Answer

Solution code:
#C
n = int(input())
a1 = []
a2 = []
for i in range(n):
    ai = int(input())
    if i % 2 == 0:
        a1.append(ai)
    else:
        a2.append(ai)

a1.sort()
a2.sort()

cnt = 0
for i in range(n // 2):
    if a1[i] > a2[i]:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(input()) for _ in range(n)]
b = sorted(a)
change=0
while (b != a):
    change=0
    for i in range(0,len(a)-2):
        if a[i] > a[i+2]:
            a[i],a[i+2] = a[i+2],a[i]
            change+=1
    if change == 0:
        for i in range(0,len(a)-1):
            if a[i]>a[i+1]:
                a[i],a[i+1]=a[i+1],a[i]
                change+=1
print(str(change))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    L = []
    for i in range(N):
        L += [int(input())]
    S = sorted(L)
    A = sorted(L[0::2])
    B = sorted(L[1::2])
    cnt = 0
    for i in range(N):
        if (i+1) % 2 == 1:
            if A[i//2] != S[i] : cnt += 1
        else:
            if B[i//2] != S[i] : cnt += 1
    print(cnt // 2)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    L = []
    for i in range(N):
        L += [int(input())]
    S = sorted(L)
    A = sorted(L[0::2])
    B = sorted(L[1::2])
    cnt = 0
    for i in range(N):
        if i % 2 == 0:
            if A[i//2] != S[i]: cnt += 1
        else:
            if B[i//2] != S[i]: cnt += 1
    print(cnt // 2)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def solve(A):
  A0 = [A[i] for i in range(0, len(A), 2)]
  A1 = [A[i] for i in range(1, len(A), 2)]
  A0.sort()
  A1.sort()
  result = 0
  i0, i1 = 0, 0
  a0 = A0[0]
  a1 = A1[0]
  for pos in range(len(A)):
    if pos%2 == 0:
      if a0 < a1:
        i0 += 1
        if i0 == len(A0): break
        a0 = A0[i0]
      else: 
        result += 1
        a1 = a0
        i1 += 1
        if i1 == len(A1): break
        a0 = A1[i1]
    else:
      if a1 < a0:
        i1 += 1
        if i1 == len(A1): break
        a1 = A1[i1]
      else: 
        result += 1
        a0 = a1
        i0 += 1
        if i0 == len(A0): break
        a1 = A0[i0]
  return result
 
N=int(input())
A=[int(input()) for i in range(N)]
print(solve(A))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !
n = int(input())
ls = []
for i in range(n):
    ls.append(int(input()))
inx = 0
ans = 0
while inx < n and ls != []:
    # i は最小が確定したindex
    inx = 0
    if n == 1:
        print(0)
        break
    if n == 2:
        if ls[0] < ls[1]:
            print(0)
            break
        else:
            print(1)
            break
    for i in range(n - 2):
        if i == 0 and ls[0] == min(ls):
            inx = 1
            break
        if i == 1 and ls[1] == min(ls):
            ls[i], ls[i - 1] = ls[i - 1], ls[i]
            inx = 1
            ans += 1
            break
        if ls[i] > ls[i + 2]:
            ls[i], ls[i + 2] = ls[i + 2], ls[i]
        #print(ls, inx)
    ls = ls[inx:]
print(ans)

Submission status: Wrong Answer

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
            print A[i]
    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: Wrong Answer

Solution code:
ans = 0

j = 0

N = int(raw_input())

A, B, C= [], [], []

for i in range(N):
  A.append(int(raw_input()))

for i in range(N):
  if i % 2 == 0:
    B.append(A[i])

  if i % 2 == 1:
    C.append(A[i])

B.sort()
B.reverse()

C.sort()
C.reverse()

for i in range(N):
  if i % 2 == 0:
    A[i] = B[j]

  if i % 2 == 1:
    A[i] = C[j]
    j += 1

for i in range(N - 1):
  if A[i] < A[i + 1]:
    A[i], A[i + 1] = A[i + 1], A[i]
    ans += 1

print ans

Submission status: Wrong Answer

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=[0]*(n/2+n%2)
b=[0]*(n/2)
c=[0]*n
cs=[0]*n
cnt=long(0)
for j in range(n/2):
    a[j]=i()
    b[j]=i()
if n%2==1:
    a[n/2]=i()
    
a.sort()
d=[i*2 for i in range(len(a))]+([-1]*len(b))
c=zip(a+b,d)
c.sort()

for (i,x) in enumerate(c):
    if x[1] != -1:
        cnt += abs(i-x[1])

print cnt

Submission status: Wrong Answer

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=[0]*(n/2+n%2)
b=[0]*(n/2)
c=[0]*n
cs=[0]*n
cnt=0
for j in range(n/2):
    a[j]=i()
    b[j]=i()
if n%2==1:
    a[n/2]=i()
    
a.sort()
d=[i*2 for i in range(len(a))]+([-1]*len(b))
c=zip(a+b,d)
c.sort()

for (i,x) in enumerate(c):
    if x[1] != -1:
        cnt += abs(i-x[1])

print cnt

Submission status: Wrong Answer

Solution code:
def solve():
    n = int(input())
    e = [0] * ((n + 1) // 2)
    o = [0] * (n // 2)
    a = [0] * n
    for i in range(n):
        n_ = int(input())
        if i % 2 == 0:
            e[i // 2] = n_
        else:
            o[i // 2] = n_
        a[i] = n_
    e.sort()
    o.sort()
    a.sort()
    b = [0] * n
    indices = {}
    for i in range(n):
        indices[a[i]] = i
        b[i] = e[i // 2] if i % 2 == 0 else o[i // 2]
    ans = 0
    for i in range(n):
        ans += abs(i - indices[b[i]])
    print(ans // 2)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def solve(A):
  A0 = [A[i] for i in range(0, len(A), 2)]
  A1 = [A[i] for i in range(1, len(A), 2)]
  A0.sort()
  A1.sort()
  result = 0
  for pos in range(len(A) // 2):
    a0 = A0[pos]
    a1 = A1[pos]
    if a0 > a1: result += 1
  return result

N=int(input())
A=[int(input()) for i in range(N)]
print(solve(A))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(raw_input())
A = []
for i in xrange(N):
    A.append(int(raw_input()))
A = np.array(A)
if np.argmin(A) % 2 == 0:
    print 0
else:
    print 1

Submission status: Wrong Answer

Solution code:
def solve():
    n = int(input())
    e = [0] * ((n + 1) // 2)
    o = [0] * (n // 2)
    a = [0] * n
    for i in range(n):
        n_ = int(input())
        if i % 2 == 0:
            e[i // 2] = n_
        else:
            o[i // 2] = n_
        a[i] = n_
    e.sort()
    o.sort()
    a.sort()
    ans = 0
    for i in range(n):
        if i % 2 == 0:
            if a[i] != e[i // 2]:
                ans += 1
        else:
            if a[i] != o[i // 2]:
                ans += 1
    print((ans + 1) // 2)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def solve():
    n = int(input())
    e = [0] * ((n + 1) // 2)
    o = [0] * (n // 2)
    a = [0] * n
    for i in range(n):
        n_ = int(input())
        if i % 2 == 0:
            e[i // 2] = n_
        else:
            o[i // 2] = n_
        a[i] = n_
    e.sort()
    o.sort()
    a.sort()
    ans = 0
    for i in range(n):
        if i % 2 == 0:
            if a[i] != e[i // 2]:
                ans += 1
        else:
            if a[i] != o[i // 2]:
                ans += 1
    print(ans // 2)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = input()
a = []
b = []
for _ in xrange(n):
    if _%2 == 0:
        a.append(input())
    else:
        b.append(input())
a = sorted(a)
b = sorted(b)
c = 0
i = j = 0
k = 0
while i < len(a) and j < len(b):
    # print i,j ,a[i],b[j]
    # print min(a[i],b[j])
    if a[i] < b[j] and k%2 == 1: #odd
        c += 1
        i +=1
    elif a[i] > b[j] and k%2 == 0: #even
        c += 1
        j += 1
    elif a[i] < b[j]:
        i += 1
    else:
        j += 1
    k += 1
print (c+1)/2

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
if N % 2 == 0:
    print 1
else:
    print 0

Submission status: Wrong Answer

Solution code:
ans = 0

N = int(raw_input())

A = []

for i in range(N):
  A.append(int(raw_input()))

for i in range(N - 2):
  if A[i] < A[i + 2]:
    A[i], A[i + 2] = A[i + 2], A[i]

for i in range(N - 1):
  if A[i] < A[i + 1]:
    A[i], A[i + 1] = A[i + 1], A[i]
    ans += 1

print ans

Submission status: Wrong Answer

Solution code:
from sys import stdin
from heapq import heappush, heappop, heapify
n = int(stdin.readline())
a = [int(stdin.readline()) for _ in xrange(n)]
b = a[0::2]
c = a[1::2]
b.sort()
c.sort()
heapify(b)
heapify(c)
d = [b, c]
ans = t = 0
a.sort()
for x in a:
    y = heappop(d[t])
    t = 1 - t
    if y != x:
        ans += 1
	heappop(d[t])
        heappush(d[t], y)
print ans