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 sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n = int(readline())
a = [int(readline()) for i in range(n)]
k = [ai for i,ai in enumerate(a) if i%2 == 0]
g = [ai for i,ai in enumerate(a) if i%2 == 1]
k.sort()
g.sort()
ans = 0
if n%2 == 1:
  g = g+[10**9]
for i in range(len(k)):
  if i != len(k)-1:
    if min(k[i],k[i+1]) > g[i]:
      k[i+1] = max(k[i],k[i+1])
      ans += 1
    elif max(k[i],k[i+1]) < g[i]:
      k[i+1] = g[i]
      ans += 1
  else:
    if k[i] > g[i]:
      ans += 1
    
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.readline().rstrip())

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

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

A.sort()
odd_seq.sort()
# even_seq.sort()

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
A = [[],[]]
for i in range(n):
    a = int(input())
    A[i%2].append(a)
A[0].sort()
A[1].sort()
i = 0
j = 0
ans = 0
while i < len(A[0]) and j < len(A[1]):
    if i == j:
        ans += A[0][i] > A[1][j]
        i += 1
    else:
        ans += A[0][i] < A[1][j]
        j += 1
print(ans)

Submission status: Wrong Answer

Solution code:
class SegTree():
    def __init__(self, N, e=0, operator_func=lambda x,y:x+y):
        self.e = e

        self.N = N
        bitlen = (N).bit_length()
        self.size = 2**(bitlen if N&(N-1) else bitlen-1)
        self.node = [self.e] * (2*self.size)
        self.op = operator_func

    def set_list(self, l):
        for i,j in enumerate(l):
            self.node[i+self.size-1] = j
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


N = int(input())
if N==1:
    print(0)
else:
    l1, l2 = [], []
    for i in range(N):
        a = int(input())
        if i%2:
            l2.append(a)
        else:
            l1.append(a)
    l1.sort()
    l2.sort()
    l = [l2[i//2] if i%2 else l1[i//2] for i in range(N)]
    tree = SegTree(N)
    d = {j:i for i,j in enumerate(sorted(l))}
    ans = 0
    
    for i, j in enumerate(l):
        tree.update(d[j], 1)
        ans += (i-tree.get(0, d[j]))
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

if N==1:
    print(0)
else:
    l1, l2 = [], []
    for i in range(N):
        a = int(input())
        if i%2:
            l2.append(a)
        else:
            l1.append(a)
    l1.sort()
    l2.sort()
    l = [l2[i//2] if i%2 else l1[i//2] for i in range(N)]
    m = [l2[i//2] if i%2 else l1[i//2] for i in range(N)]
    v1, v2 = 0, 0

    for i in range(N-1):
        if l[i] > l[i+1]:
            v1 += 1
            l[i], l[i+1] = l[i+1], l[i]
    for i in range(N-1)[::-1]:
        if m[i] > m[i+1]:
            v2 += 1
            m[i], m[i+1] = m[i+1], m[i]
    ans = min(v1, v2)
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

if N==1:
    print(0)
else:
    l1, l2 = [], []
    for i in range(N):
        a = int(input())
        if i%2:
            l2.append(a)
        else:
            l1.append(a)
    l1.sort()
    l2.sort()
    l = [l2[i//2] if i%2 else l1[i//2] for i in range(N)]
    ans = 0
    for i in range(N-1):
        if l[i] > l[i+1]:
            ans += 1
            l[i], l[i+1] = l[i+1], l[i]
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import chain


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

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

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

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_


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)
even = sorted(aaa[0::2])
odd = sorted(aaa[1::2])
aaa = list(chain.from_iterable(zip(even, odd)))
if n % 2 == 1:
    aaa.append(even[-1])

ans = 0
bit = Bit(len(d))
for a in reversed(aaa):
    ans += bit.sum(a + 1)
    bit.add(a + 2, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

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




n = int(input())
b=[]
c=[]
a=[]
for i in range(n):
    a.append(int(input()))
    if(i%2==0): b.append(a[-1])
    else: c.append(a[-1])

b.sort()
c.sort()

for i in range(len(b)):
    a[i*2]=b[i]
for i in range(len(c)):
    a[1+i*2] = c[i]

#print(a)

aa = [[a[i],i]for i in range(n)]

aa.sort(key = lambda x : x[0])
for i in range(n):
    aa[i][0]=i+1
aa.sort(key = lambda x : x[1])
#print(aa)

bit = Bit(n*2+1)
ans = 0
for i in range(n):
    val = aa[n-1-i][0]
    ans += bit.sum(val)
    bit.add(val,1)
    

print(ans)

Submission status: Wrong Answer

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
    t = 0
    for i, (_, j) in enumerate(A):
        if j == 0:
            res += abs(i - (t * 2))
            t += 1

    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    print(A)
    res = 0
    t = 0
    for i, (_, j) in enumerate(A):
        if j == 0:
            res += abs(i - (t * 2))
            t += 1

    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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
    t = [0, 0]
    for a, i in A:
        if i == 0:
            res += max(0, t[0] - t[1])
            t[0] += 1
        else:
            t[1] += 1
            res += max(0, t[1] - t[0])

    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

ans=0
for i in range(0,len(a)):
    ans+=abs(dic[a[i]]-2*i-1)

print(ans)

Submission status: Wrong Answer

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

Solution code:
n = int(input())

a = []

for i in range(n):
	x = int(input())
	a.append(x)
a.sort()

cnt = 0

for i, j in enumerate(a):
	if j % 2 != i % 2:
		cnt += 1
print(cnt // 2 - 1)

Submission status: Wrong Answer

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 = [dic[k] for k in kl]

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

al = sorted(al)
bl = sorted(bl)

A = []
for i in range(n):
    if i % 2 == 0:
        A.append(al[i//2])
    else:
        A.append(bl[i//2])

N = n

# BIT
data = [0]*(N+1)
def add(k, x):
    while k <= N:
      data[k] += x
      k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

ans = 0
for i, a in enumerate(A):
    # 自分より小さい要素がいくつ存在するかを計算
    ans += (N-1-i) - get(a)
    add(a, 1)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class BIT:
  def __init__(self, n):
    self.N = n+1
    self.bit = [0]*self.N
  
  def bit_sum(self, i):
    s = 0
    i += 1
    while i>0:
      s += self.bit[i]
      i -= i & -i
    return s

  def bit_add(self, i, n):
    i += 1
    while i<self.N:
      self.bit[i] += n
      i += i & -i
N, *A = map(int, open(0).read().split())
X = A[0::2]
Y = A[1::2]
X.sort()
Y.sort()
Z = [X[i//2] if i%2==0 else Y[i//2] for i in range(N)]
bit = BIT(N)
dic = {}
for i in range(N):
  bit.bit_add(i,1)
  dic[Z[i]] = i
ans = 0
A.sort(reverse=True)
for i,m in enumerate(A):
  c = bit.bit_sum(dic[m])
  if c==N-i:
    continue
  bit.bit_add(dic[m],-1)
  ans += N-i-c
print(ans)

Submission status: Wrong Answer

Solution code:
class BinaryIndexedTree(): #1-indexed
    def __init__(self,n):
        self.n = n
        self.tree = [0 for _ in range(self.n+1)]

    def sum(self,index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res

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

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

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

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

bit = BinaryIndexedTree(N+1)

count = 0

for i in range(N):
    bit.add(D[B[i]],1)
    count += i+1-bit.sum(D[B[i]])

print(count)

Submission status: Wrong Answer

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]

A.sort()
odd.sort()
even.sort()
ans=0

for i in range(0,N,2):
  if A[i]!=odd[i//2]:
    ans+=1
tmp=0
for i in range(1,N,2):
  if A[i]!=even[i//2]:
    tmp+=1

print(max(ans,tmp))

Submission status: Wrong Answer

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]
A.sort()
odd.sort()
ans=0
for i in range(0,N,2):
  if A[i]!=odd[i//2]:
    ans+=1
print(ans)

Submission status: Wrong Answer

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

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()
    print(odd,al)
    ans = 0
    for i in range(N//2):
        if al[2*i+1] in odd:
            ans += 1
            
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    N =  int(input())
    
    odd,even = [],[]
    for i in range(N):
        a = int(input())
        if i%2 == 0:
            odd.append(a)
        else:
            even.append(a)
            
    odd.sort()
    even.sort()
    l = len(even)
    ans = 0
    for i in range(l):
        now = i+1
        num = even[i]
        ins = bisect.bisect_left(odd,num)
        ans += abs(now-ins)
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
5
10
8
5
3
2

Submission status: Wrong Answer

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

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:
    ans += abs(k-now*2)
    now += 1
  if now == br:
    break
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

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

S = sorted(range(len(A)), key=lambda k:A[k])
s = 0
for i in range(N):
    s += abs(S[i]-i)

if s%4==0:
    print(0)
else:
    print(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_right(a, b[i]) - i - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
import copy

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

#処理内容
def main():
	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])
	ans1 = 0
	ans2 = 0
	D = copy.deepcopy(C)
	E = copy.deepcopy(C)
	for i in range(N - 1):
		if D[i] > D[i + 1]:
			ans1 += 1
			D[i + 1], D[i] = D[i], D[i + 1]
	for i in range(N - 1):
		if E[-2 - i] > E[-1 - i]:
			ans2 += 1
			E[-1 - i], E[-2 - i] = E[-2 - i], E[-1 - i]

	print(min(ans1, ans2))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

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

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

B0.sort()
B1.sort()

C = []
for i in range(N//2):
    C += [B0[i], B1[i]]
if N%2 == 1:
    C.append(B0[-1])

# AOJ ALDS1_5_D "The Number of Inversions"
# 転倒数をO(NlogN)で求める

# binary indexed tree
bit = [0 for _ in range(N+1)]

# 0からiまでの区間和
# 立っているビットを下から処理
def query_sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

# i番目の要素にxを足す
# 覆ってる区間すべてに足す
def add(i, x):
    while i <= N:
        bit[i] += x
        i += i & -i

# 座標圧縮
ind_to_co = sorted(A)
co_to_ind = {}
for i, x in enumerate(ind_to_co):
    co_to_ind[x] = i+1

# それまでに「i<=jかつai<=aj」となっているものをBITに加えていく
ans = 0
for j, a in enumerate(C):
    ind_a = co_to_ind[a]
    ans += j - query_sum(ind_a)
    add(ind_a, 1)

print(ans)

Submission status: Wrong Answer

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

print(ans)
# print(A)

Submission status: Wrong Answer

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

print(ans)
# print(A)

Submission status: Wrong Answer

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

# print(even)
# print(odd)
even = sorted(even)
odd = sorted(odd)
for j in range(N // 2):
    if odd[j] < even[j]:
        ans += 1
    elif odd[j] > even[j + 1]:
        ans += 1

print(ans)
# print(A)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect

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()
        c=[]
        t=0
        res = 0
        for i in range(n//2):
            res += t - bisect.bisect_left(c,a[i])
            bisect.insort_left(c,a[i])
            t += 1
            res += t - bisect.bisect_left(c,b[i])
            bisect.insort_left(c,b[i])
            t += 1
        if n % 2 == 1:
            res += t - bisect.bisect_left(c,a[-1])
            bisect.insort_left(c,a[-1])
            t += 1
        print(res)
main()

Submission status: Wrong Answer

Solution code:
import bisect

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()
        c=[]
        t=0
        res = 0
        for i in range(n//2):
            res += t - bisect.bisect_left(c,a[i])
            bisect.insort_left(c,a[i])
            t += 1
            res += t - bisect.bisect_left(c,b[i])
            bisect.insort_left(c,b[i])
            t += 1
        if n % 2 == 1:
            res += t - bisect.bisect_left(c,a[i])
            bisect.insort_left(c,a[i])
            t += 1
        print(res)
main()

Submission status: Wrong Answer

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

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:
            res = 1

        for i in range(1,n//2):
            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: Wrong Answer

Solution code:
from bisect import bisect_left

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

a1, a2 = a[::2], a[1::2]
a1.sort()
a2.sort()
ans = 0

for i in range(len(a2)):
    ans += abs(bisect_left(a1, a2[i]) - (i + 1))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

idx_A = {}
for i in range(N):
    idx_A[A[i]] = i

B = tuple(sorted(A))

ans = 0
skip_flag = False
for i in range(N):
    if skip_flag == False:
        #idx = A.index(B[i])
        if abs(i - idx_A[B[i]]) % 2 == 0: # あまり０なら操作２だけで所定の位置に動かせる
            continue
        else:
            ans += 1
            # 次のやつも同時にできるか
            if i < N-1:
                #next_idx = A.index(B[i+1])
                if abs(i+1 - idx_A[B[i+1]]) % 2 == 1:
                    skip_flag = True
    else:
        skip_flag = False
        continue

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    b = sorted(a)
    c = b[::2]
    d = a[::2]
    set_c = set(c)
    set_d = set(d)
    print(len(set_c & set_d))

main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    b = sorted(a)
    c = [a[i] for i in range(n) if a.index(b[i])%2 == 1]
    print(int(len(c)/2))
main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [int(input()) for _ in range(n)]
ss = sorted(s)
d = {ss[i]: i for i in range(n)}
ans = 0
for i, j in enumerate(s):
    ans += i % 2 != d[j] % 2
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [int(input()) for _ in range(n)]
ss = sorted(s)


def find(x):
    a, b = 0, len(ss) - 1
    while a != b:
        if ss[(a + b) // 2] <= x:
            b = (a + b) // 2
        else:
            a = (a + b) // 2 + 1
    return a


ans = 0
print(ss)
for i, j in enumerate(s):
    ans += i % 2 != find(j) % 2
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())

ki=[]
gu=[]
for i in range(n):
    if i%2==0:
        ki.append(int(input()))
    else:
        gu.append(int(input()))
ki.sort()
gu.sort()

awa=[]
for i in range(n):
    if i%2==0:
        awa.append(ki.pop(0))
    else:
        awa.append(gu.pop(0))

sawa=sorted(awa)

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

Submission status: Wrong Answer

Solution code:
n=int(input())

ki=[]
gu=[]
for i in range(n):
    if i%2==0:
        ki.append(int(input()))
    else:
        gu.append(int(input()))
ki.sort()
gu.sort()

awa=[]
for i in range(n):
    if i%2==0:
        awa.append(ki.pop(0))
    else:
        awa.append(gu.pop(0))

sawa=sorted(awa)

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return

#B
def B():
    n = I()
    a = IR(n)
    ans = 0
    b = [0]*(n+1)
    for i in range(n):
        ans += (a[i]+b[i])>>1
        if (a[i]%2)^(b[i]%2) and a[i]:
            b[i+1] += 1
    print(ans)
    return

#C
def C():
    def add(i):
        while i <= n:
            bit[i] += 1
            i += i&-i

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res

    n = I()
    bit = [0]*(n+1)
    a = IR(n)
    b = [(a[i],i) for i in range(n)]
    b.sort()
    for i in range(n):
        a[b[i][1]] = i+1
    f = [1]*n
    j = 0
    ans = 0
    for i in range(n):
        if a[i]%2 != i%2:
            f[i] = 0
        else:
            ans += j-sum(a[i])
            add(a[i])
            j += 1
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

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

Submission status: Wrong Answer

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