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

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

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


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

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

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


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

print(ans)

Submission status: Runtime Error

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

I,O,T,J,L,S,Z = map(int,input().split())

# T,S,Z は無関係
# I,O,J,Lに注目
# Oは足すだけ
# I,J,Lが問題
# II, JIL, JJ, LL

x = (I//2 + J//2 + L//2) * 2
if I>0 and J>0 and L>0:
    x = max(x,((I-1)//2 + (J-1)//2 + (L-1)//2) * 2 + 3)
x += O

print(x)

Submission status: Runtime Error

Solution code:
#import sys
#from collections import defaultdict
input = sys.stdin.readline
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    B = sorted(A)
    d = defaultdict( int)
    for i in range(N):
        d[B[i]] = i
    odd = 0
    for i in range(N):
        if (i+1)%2 == d[A[i]]%2 and d[A[i]]%2 == 1:
            odd += 1
    print(odd)
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

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
j=0
for i in range(C):
	if A[j]==C[i]:
		if i%2==1:
			c+=1
		j+=1
print(c)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as d
a=[int(input()) for i in range(int(input()))]
b=sorted(a)
c=d(int)
e=0
for i in range(0,n,2):
    d[b[i]]=1
for i in a[1::2]:
    e+=d[i]
print(e)

Submission status: Runtime Error

Solution code:


def nibutan2(array,value,left,right,first = True):
    if first:
        if array[left]>value:
            return 0
        elif array[right]<value:
            return len(array)
    if right-left<=1:
        return right
    else:
        i=(left+right)//2
        if array[i]>value:
            return nibutan2(array,value,left,i,False)
        elif array[i]<value:
            return nibutan2(array,value,i,right,False)


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

for i in range(len(A)):
    c=nibutan2(B,A[i],0,len(B)-1)
    count+=abs(c-i)

print(count)

Submission status: Runtime Error

Solution code:
def nibutan2(array,value,left,right,first = True):
    if first:
        if array[left]>value:
            return 0
        elif array[right]<value:
            return len(array)
    if right-left<=1:
        return right
    else:
        i=(left+right)//2
        if array[i]>value:
            return nibutan(array,value,left,i,False)
        elif array[i]<value:
            return nibutan(array,value,i,right,False)


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

for i in range(len(A)):
    c=nibutan2(B,A[i],0,len(B)-1)
    count+=abs(c-i)

print(count)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
int n, k[100005], mon[100005], ans;
bool pre(int a, int b) {
    if(k[a]<k[b]){return true;}
    else{return false;}
}

int main() {
	cin>>n;
	for (int i = 0; i < n; ++i) {
		cin>>k[i];
        mon[i+1] = i+1;
	}
    sort(mon,mon+n,pre);
	for (int i = 0; i < n; i += 2){
		if (mon[i+1] % 2 == 0){++ans;}
    }
	cout<<ans<<endl;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N=int(input())
l=[int(input()) for _ in range(N)]
cnt=0
if(N<3):
    if N==1:print("0")
    elif l[1]>l[2]: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: Runtime Error

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

	a1 = set(a1)
	b1 = set(b1)

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

Submission status: Runtime Error

Solution code:
#coding: cp932
N = int(input())
inp =[]
for s in range(N):
	inp.append(int(input()))
check = inp[:]
check.sort()
flag=1
s,ans,lis2 = 0,0,[]

while flag==1:
	#lis.append(check[s])
	lis2.append(inp[s])
	s+=2
	if s>N-1:
		flag=0
num =len(lis)
#print(lis)
#print(lis2)
for s in range(num):
	if s!=0:
		if check[s+2] not in lis2:
			ans+=1
			lis[s] =-1
		continue
	else:
		if check[s] not in lis2:
			ans+=1
			lis[s]=-1
print(ans)