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:
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(n)
    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())
comp = {a: i for i, a in enumerate(sorted(A), 1)}
comp_A = [comp[a] for a in A]
triplet_sorted_A = [0] * N
triplet_sorted_A[::2] = sorted(comp_A[::2])
triplet_sorted_A[1::2] = sorted(comp_A[1::2])
print(get_invnum(triplet_sorted_A))

Submission status: Wrong Answer

Solution code:
from collections import deque
f = []
s = []
N = int(input())
for k in range(N):
    if k%2 == 0:
        f.append(int(input()))
    else:
        s.append(int(input()))
ans = 0
f.sort()
s.sort()
f = deque(f)
s = deque(s)
temp = []

for k in range(N):
    if k%2 == 0:
        temp.append(f.popleft())
    else:
        temp.append(s.popleft())
ans = 0
for k in range(1,N):
    if temp[k-1] > temp[k]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.msb = 1 << (size.bit_length()-1)
    
    def _add(self, i, w):
        i += 1
        while i < len(self.data):
            self.data[i] += w
            i += i & -i
    
    def _get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            if i.start is None:
                return self._get_sum(i.stop)
            else:
                return self._get_sum(i.stop) - self._get_sum(i.start)
        else:
            return 0 # fake value
    
    __setitem__ = _add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right

def count_inversions(A):
    N = len(A)
    bit = BinaryIndexedTree(N)

    inversions = 0
    for a in A:
        inversions += bit[a:N]
        bit[a] += 1
    return inversions

def solve(A):
    N = len(A)
    S = sorted(A)
    A = [bisect_left(S,a) for a in A]

    evens = sorted(A[::2])
    odds = sorted(A[1::2])

    A = [evens[i//2] if i%2==0 else odds[i//2] for i in range(N)]
    return count_inversions(A)

from itertools import permutations
min2 = lambda x,y: x if x < y else y
def naive(A):
    N = len(A)
    evens = A[::2]
    odds = A[1::2]
    m = float('inf')
    best = None
    for pe in permutations(evens):
        for po in permutations(odds):
            A = [pe[i//2] if i%2==0 else po[i//2] for i in range(N)]
            r = count_inversions(A)
            if m > r:
                m = r
                best = A
    return m,best

if __name__ == '__main__':
    N = int(input())
    A = list(int(input()) for _ in range(N))
    print(solve(A))

    # from random import shuffle

    # A = list(range(6))
    # for i in range(10000):
    #     print(i)
    #     shuffle(A)
    #     r1 = solve(A)
    #     r2,b = naive(A)
    #     if r1 != r2:
    #         print(A,b)
    #         print(r1,r2)
    #         break

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.msb = 1 << (size.bit_length()-1)
    
    def _add(self, i, w):
        i += 1
        while i < len(self.data):
            self.data[i] += w
            i += i & -i
    
    def _get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            if i.start is None:
                return self._get_sum(i.stop)
            else:
                return self._get_sum(i.stop) - self._get_sum(i.start)
        else:
            return 0 # fake value
    
    __setitem__ = _add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right


def solve(A):
    N = len(A)
    S = sorted(A)

    for i,a in enumerate(A):
        A[i] = bisect_left(S,a)

    evens = sorted(A[::2])
    odds = sorted(A[1::2])

    A = [evens[i//2] if i%2==0 else odds[i//2] for i in range(N)]

    bit = BinaryIndexedTree(N)

    inversions = 0
    for a in A:
        inversions += bit[a:N]
        bit[a] += 1
    return inversions



if __name__ == '__main__':
    N = int(input())
    A = list(int(input()) for _ in range(N))
    print(solve(A))

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from operator import itemgetter
input = sys.stdin.readline
 

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l


def compress(lis, n=2, last_sort=False):
    length = len(lis)
    first_value = -1
    for i in range(n):
        lis.sort(key=itemgetter(i))
        value = first_value
        index = 0
        for j in range(length):
            if lis[j][i] != value:
                index += 1
            value = lis[j][i]
            lis[j][i] = index
    
    if last_sort: lis.sort()
    return lis
               

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    
    odd = a[::2]
    even = a[1::2]
    
    odd.sort()
    even.sort()
    
    b = [[even[i//2], i] if i%2 else [odd[i//2], i] for i in range(n)]
    compress(b)

    ans = 0
    bit = BIT(n)
    for i in range(n):
        ans += i-bit.sum(b[i][0])
        bit.add(b[i][0], 1)
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    
    odd = a[::2]
    even = a[1::2]
    
    odd.sort()
    even.sort()
    
    b = [(even[i//2], i) if i%2 else (odd[i//2], i) for i in range(n)]
    b.sort()
    
    ans = 0
    for rank, (value, index) in enumerate(b):
        ans += max(0, index-rank)
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    
    odd = a[::2]
    even = a[1::2]
    
    odd.sort()
    even.sort()
    
    
    ans = 0
    for i, v in enumerate(odd):
        ans += bisect.bisect(even[i:], v)
    
    print(ans)
    

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    
    odd = a[::2]
    even = a[1::2]
    
    odd.sort()
    even.sort()
    
    b = [even[i//2] if i%2 else odd[i//2] for i in range(n)]
    
    ans = 0
    for i in range(n-1):
        if b[i] > b[i+1]:
            ans += 1
    
    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    
    odd = a[::2]
    even = a[1::2]
    
    odd.sort()
    even.sort()
    
    ans = 0
    for i in range(n//2):
        if odd[i] > even[i]:
            ans += 1
        if n%2 and even[i] > odd[i+1]:
            ans += 1

    
    print(ans)
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

B = A[::2]
C = A[1::2]

B.sort()
C.sort()

D = []

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

E = D[:]

E.sort()

d = {}

for i in range(N):
    d[E[i]] = i

ans = 0

for i in range(N):
    ans += max(0, d[D[i]] - i)

print(ans)

Submission status: Wrong Answer

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

B = A[::2]
C = A[1::2]

B.sort()
C.sort()

D = []

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

def bubble_sort(arr):
    cnt = 0
    change = True
    while change:
        change = False
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                cnt += 1
                change = True
    return cnt

ans = bubble_sort(D)

print(ans)

Submission status: Wrong Answer

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

import numpy as np

n = int(input())
l = [int(input()) for _ in range(n)]
l = np.array(l)
for i in range(2):
    ll = l[i::2]
    ll.sort()
    l[i::2] = ll
ret = l[1:]-l[:-1]
print(np.count_nonzero(ret < 0))

Submission status: Wrong Answer

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

B=sorted(A[::2])
C=sorted(A)
dic={}
for i in range(n):
    dic[C[i]]=i

ans=0
for i in range(len(B)):
    ans+=abs(dic[B[i]]-2*i)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = []
for i in range(n):
    lst1.append([int(readline()),i])

lst2 = sorted(lst1)
lst3 = [0]*n #lst2の規格に統一

for i,(j,k) in enumerate(lst2):
    if even(i):
        if not even(k):
            lst3[i] = 1
    else:
        if even(k):
            lst3[i] = 1

ans = 0

fl = 0
for i in range(n):
    if lst3[i] and fl:
        ans += 1
        fl = 0
    elif lst3[i]:
        fl = 1
    elif fl:
        ans += 1
        fl = 0

if fl:
    ans+= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n=int(input())
a=[int(input()) for i in range(n)]
b=a[::2]
c=a[1::2]
b.sort()
c.sort()
ans=0
for i in range(n//2):
	ans+=abs(min(bisect_left(b,c[i]),bisect_right(b,c[i]))-(i+1))
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n=int(input())
a=[int(input()) for i in range(n)]
b=a[::2]
c=a[1::2]
b.sort()
ans=0
for i in range(n//2):
	ans+=abs(min(bisect_left(b,c[i]),bisect_right(b,c[i]))-(i+1))
print(ans)

Submission status: Wrong Answer

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//2] if i&1 else b[i//2] 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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a =[int(input()) for i in range(n)]
res = [[a[i],i]for i in range(n)]
res.sort()
ret =0
for i in range(n):
    if res[i][1]%2 != i%2:ret+=1
print(ret)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = [[int(readline()), i] for i in range(1, n + 1)]
    a.sort(reverse=True)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = [[int(readline()), i] for i in range(n)]
    a.sort(reverse=True)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=[int(input()) for i in range(n)]
ki,gu=[],[]
for i in range(n):
    if i%2==0:
        ki.append(a[i])
    else:
        gu.append(a[i])
heapq.heapify(ki)
heapq.heapify(gu)
cnt=0
ans=0
# print(ki,gu)
while ki and gu:
    if cnt%2==0:
        if ki[0]<gu[0]:
            heapq.heappop(ki)
        else:
            tmp=heapq.heappop(ki)
            heapq.heappushpop(gu,tmp)
            ans+=1
    else:
        if gu[0]<ki[0]:
            heapq.heappop(gu)
        else:
            tmp=heapq.heappop(gu)
            heapq.heappushpop(ki,tmp)
            ans+=1
    cnt+=1
    # print(ki,gu)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = [ini() for _ in range(N)]


def solve():
    a0 = list(A[::2])
    a0.sort()
    a1 = list(A[1::2])
    a1.sort()
    i = j = 0
    cnt = 0
    for k in range(N):
        if i < len(a0) and j < len(a1):
            if a0[i] < a1[j]:
                cnt += max(2 * i - k, 0)
                i += 1
            else:
                cnt += max(2 * j + 1 - k, 0)
                j += 1
        elif i < len(a0):
            cnt += max(2 * i - k, 0)
            i += 1
        elif j < len(a1):
            cnt += max(2 * j + 1 - k, 0)
            j += 1
    return cnt


print(solve())

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = [ini() for _ in range(N)]


def solve():
    a0 = list(A[::2])
    a0.sort()
    a1 = list(A[1::2])
    a1.sort()
    b = [0] * N
    for i in range(N):
        if i % 2 == 0:
            b[i] = a0[i // 2]
        else:
            b[i] = a1[i // 2]
    cnt = 0
    for i in range(N - 1):
        if b[i] > b[i + 1]:
            b[i], b[i + 1] = b[i + 1], b[i]
            cnt += 1
    return cnt


print(solve())

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):  # 区間 [1, i]の和
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):  # iにxを加算
        while i <= self.size:
            self.tree[i] += x
            i += i & -i  
    def pos(self, idx):  # idxの値を取得
        return self.sum(idx) - self.sum(idx-1)

N = INT()
A = [INT() for _ in range(N)]

even = []
odd = []

for i, a in enumerate(A):
    if i%2 == 0:
        even.append(a)
    else:
        odd.append(a)

even.sort(reverse=True)
odd.sort(reverse=True)
zipped = {x:i+1 for i, x in enumerate(sorted(set(A)))}

B = []
while even:
    B.append(zipped[even.pop()])
    if odd:
        B.append(zipped[odd.pop()])
    else:
        break

bit = Bit(N)

ans = 0
for i, b in enumerate(B):
    ans += i-bit.sum(b)
    bit.add(b, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()
    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret
    def bitsum(self, l, r=None):
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)
    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return
    def lower_bound(self, x):  # w以上の値を持つ最小のidxを検索
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos

N = INT()
A = [INT() for _ in range(N)]

even = []
odd = []

for i, a in enumerate(A):
    if i%2 == 0:
        even.append(a)
    else:
        odd.append(a)

even.sort(reverse=True)
odd.sort(reverse=True)
zipped = {x:i+1 for i, x in enumerate(sorted(set(A)))}

B = []
while even:
    B.append(zipped[even.pop()])
    if odd:
        B.append(zipped[odd.pop()])
    else:
        break

bit = BIT(N)

ans = 0
for i, b in enumerate(B):
    ans += i-bit.bitsum(b)
    bit.bitadd(b, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()
    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret
    def bitsum(self, l, r=None):
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)
    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return
    def lower_bound(self, x):  # w以上の値を持つ最小のidxを検索
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos

N = INT()
A = [INT() for _ in range(N)]

even = []
odd = []

for i, a in enumerate(A):
    if i%2 == 0:
        even.append(a)
    else:
        odd.append(a)

even.sort(reverse=True)
odd.sort(reverse=True)
zipped = {x:i for i, x in enumerate(sorted(set(A)))}

B = []
while even:
    B.append(zipped[even.pop()])
    if odd:
        B.append(zipped[odd.pop()])
    else:
        break

bit = BIT(N)

ans = 0
for i, b in enumerate(B):
    ans += i-bit.bitsum(b)
    bit.bitadd(b, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
def invNumCount(A):
    N = len(A)
    res = 0
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(N+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return
    
    #Aが座圧されていないとき
    #"""
    B = sorted(A)
    for i,e in enumerate(A):
        A[i] = bisect.bisect_left(B,e)
    #"""

    Ai = [None]*N
    for i,e in enumerate(A):
        Ai[e] = i
    for i,e in enumerate(Ai):
        res += i-BIT_query(e+1)
        BIT_update(e+1, 1)
    return res

n=int(input())
a=[int(input()) for i in range(n)]
b=[]
a1,a2=sorted(a[::2],reverse=1),sorted(a[1::2],reverse=1)
for i in range(n):
    if i%2==0:
        b.append(a1.pop())
    else:
        b.append(a2.pop())
print(invNumCount(b))

Submission status: Wrong Answer

Solution code:
compress3 = lambda arr: list(map({e: i for i, e in enumerate(sorted(set(arr)))}.__getitem__, arr))
n = int(input())
a = [int(input()) for i in range(n)]
a = compress3(a)
odd = set()
even = set()

for i in range(n):
    if i % 2 == 0:
        even.add(a[i])
    else:
        odd.add(a[i])

ans = len(set([2*i for i in range(n//2)]) & odd)
print(ans)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

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

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = int(input())
a = [None] * n
for i in range(n):
    a[i] = int(input())
    
from bisect import bisect_left
def press(l):
    # xs[inds[i]]==l[i]となる
    xs = sorted(set(l))
    inds = [None] * len(l)
    for i,item in enumerate(l):
        inds[i] = bisect_left(xs, item)
    return xs, inds

xs, inds = press(a)
    
odd = [num for i,num in enumerate(inds) if i%2]
even = [num for i,num in enumerate(inds) if i%2==0]

odd.sort()
even.sort()

aa = [None] * n
for i in range(n//2 + n%2):
    aa[2*i] = even[i]
for i in range(n//2):
    aa[2*i+1] = odd[i]
    
def init(bit, values):
    for i,v in enumerate(values):
        update(bit,i,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def update(bit,i,x):
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

# 1-indexedなので注意
bit = [0] * (n+1)
ans = 0
for i,ind in enumerate(aa):
    ans += (i - query(bit, ind+1))
    update(bit, ind+1, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
l1 = [a[i] for i in range(n) if i % 2 == 0]
l2 = [a[i] for i in range(n) if i % 2 == 1]
l1.sort()
l2.sort()
ans = 0
for i in range(min(len(l1), len(l2))):
    if l1[i] > l2[i]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = [NI() for _ in range(N)]
    odd = []
    even = []
    for i in range(len(A)):
        if i % 2:
            odd.append(A[i])
        else:
            even.append(A[i])

    odd.sort()
    even.sort()
    A.sort()

    BIT = [0] * (N+1)
    def add(i,x):
        while i <= N:
            BIT[i] += x
            i += i & -i

    def query(i):
        ret = 0
        while i > 0:
            ret += BIT[i]
            i -= i & -i
        return ret

    ans = 0
    for i in range(N):
        if i % 2:
            x = odd[i//2]
        else:
            x = even[i//2]

        p = bisect.bisect(A,x)
        ans += i - query(p)
        add(p, 1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = [ NI() for _ in range(N)]
    odd = []
    even = []
    for i in range(len(A)):
        if i % 2:
            odd.append(A[i])
        else:
            even.append(A[i])

    odd.sort()
    even.sort()
    A.sort()

    BIT = [0] * (N+1)
    def add(i,x):
        while i <= N:
            BIT[i] += x
            i += i & -i

    def query(i):
        ret = 0
        while i > 0:
            ret += BIT[i]
            i -= i & -i
        return ret

    ans = 0
    for i in range(N):
        if i % 2:
            x = odd[i//2]
        else:
            x = even[i//2]

        p = bisect.bisect_left(A,x) + 1
        ans += i - query(p)
        add(p, 1)
    print(ans)

if __name__ == '__main__':
    main()

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+1]
for i in range(len(k)):
  if i == 0:
    if k[i] > g[i]:
      k[i],g[i] = g[i],k[i]
      ans += 1      
  else:
    if k[i-1] > g[i-1]:
      g[i-1],k[i-1] = k[i-1],g[i-1]
      ans += 1
    elif k[i] < g[i-1]:
      k[i],g[i-1] = g[i-1],k[i]
      ans += 1
      
  if i != len(k)-1:
    if k[i] > g[i]:
      g[i],k[i] = k[i],g[i]
      ans += 1
    elif k[i+1] < g[i]:
      k[i+1],g[i] = g[i],k[i+1]
      ans += 1
  else:
    if k[i] > g[i]:
      ans += 1
    
print(ans)

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+1]
for i in range(len(k)):
  if i != len(k)-1:
    if k[i] > g[i]:
      ans += 1
    elif k[i+1] < g[i]:
      k[i+1] = g[i]
      ans += 1
  else:
    if k[i] > g[i]:
      ans += 1
    
print(ans)