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:
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 d
print ans

Submission status: Wrong Answer

Solution code:
n = input()
a = [input() for i in range(n)]
def bbubbblesort(l):
    for index in xrange(len(l)-1, 0, -1):
        for low in xrange(index-1):
            if l[low] > l[low+2]:
                tmp = l[low+2]
                l[low+2] = l[low]
                l[low] = tmp
    return l
def bubblesort(l):
    cnt = 0
    for index in xrange(len(l)-1, 0, -1):
        for low in xrange(index):
            if l[low] > l[low+1]:
                tmp = l[low+1]
                l[low+1] = l[low]
                l[low] = tmp
                cnt += 1
                print cnt
    return cnt
A = bbubbblesort(a)
print bubblesort(A)

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/2

Submission status: Wrong Answer

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

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

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

ans = 0
for i in xrange(N):
    if i % 2 != 0: continue
    if B[i] != X[i/2]:
        ans += 1
print ans

Submission status: Wrong Answer

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

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

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

A = [X[i/2] if i%2 == 0 else Y[i/2] for i in xrange(N)]
ans = 0
for i in xrange(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:
N=int(input())
a=[]
b=[]
for i in range(N):
    if(i%2):
        a.append(int(input()))
    else:
        b.append(int(input()))

a.sort()
b.sort()
count=0
for i in range(len(a)):
    if(a[i]<b[i]):
        count+=1
print(count)

Submission status: Wrong Answer

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

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

X = sorted([A[i] for i in xrange(N) if i%2 == 0], reverse = True)
Y = sorted([A[i] for i in xrange(N) if i%2 == 1], reverse = True)

ans = 0
for i in xrange(N):
    if X and Y and X[-1] > Y[-1]:
        ans += 1
        Y.pop(-1)
    elif X and not Y:
        ans += 1
        X.pop(-1)
    elif Y and not X:
        ans += 1
        Y.pop(-1)
    elif X and Y:
        X.pop(-1)
        Y.pop(-1)

print ans - 1

Submission status: Wrong Answer

Solution code:
from sys import stdin
n = int(stdin.readline())
a = [int(stdin.readline()) for _ in xrange(n)]
b = a[0::2]
c = a[1::2]
b.sort()
c.sort()
b += [-1]
c += [-1]
ans = 0
bi = ci = bl = 0
cl = 1
a.sort()
ab = abs
for i, x in enumerate(a):
    if b[bi] == x:
        bi += 1
        ans += ab(i - bl)
	bl += 2
    else:
        ci += 1
        ans += ab(i - cl)
	cl += 2
print ans / 2

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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 = [None] * 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, 0, -1):
        for j in range(i):
            if b[j] > b[i]:
                b[i], b[j] = b[j], b[i]
                cnt += 1

    return cnt


print(solve())

Submission status: Time Limit Exceeded

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

O = sorted(A)[::2]
E = sorted(A)[1::2]

ans = 0
for i in range(N):
    if i % 2 == 0 and A[i] not in O:
        ans += 1
    elif i % 2 == 1 and A[i] not in E:
        ans += 1
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

ans=0

a=[]
b=[]

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

ans=0

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

b=sorted(a)

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

Submission status: Time Limit Exceeded

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

from bisect import insort
from collections import deque

for i in range(n-1):
  K = (i+1)//2
  G = i//2
  p = k[K]; q = g[G]
  if (K == G and p > q) or (K > G and p < q):
    ans += 1
    insort(k,q)
    insort(g,p)
    k = deque(k)
    g = deque(g)
    k.popleft()
    g.popleft()
    k = list(k)
    g = list(g)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
count = 0
for i in range(N):
    a.append(int(input()))
#
flag = 1
while flag==1:
    flag = 0
    for i in range(N-2):
        if a[i]>a[i+2]:
            c = a[i]
            a[i] = a[i+2]
            a[i+2] = c
            flag = 1
#iとi+2を比較し、iの方が大きかったら入れ替える
flag =1
while flag ==1:
    flag =0
    for i in range(N-1):
        if a[i]>a[i+1]:
            c = a[i]
            a[i] = a[i+1]
            a[i+1] = c
            flag = 1
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [ri() for _ in range(N)]
B = np.array(sorted(A))
C = [np.where(B == a)[0][0] for a in A]
answer = sum([i%2==1 and x%2!=1 for i, x in enumerate(C)])
print(answer)
# 41

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = np.array([ri() for _ in range(N)])
B = sorted(A)
C = [np.where(B == a)[0][0] for a in A]
answer = sum([i%2==1 and x%2!=1 for i, x in enumerate(C)])
print(answer)
# 41

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A = [0]*(n)
for i in range(n):
    s=int(input())
    A[i]=s
    
lista=sorted(A)
cnt=0
for a in range(0,n,2):
    if A.index(lista[a])%2!=0:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
b = sorted(a)
counter = 0
for i in range(0, n, 2):
    if a.index(b[i])%2 == 1:
        counter += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [int(input()) for _ in range(n)]
os = [s[i] for i in range(0,n,2)]
j = sorted(s)
ans = 0
for i in os:
    if j.index(i) % 2 == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [int(input()) for _ in range(n)]
j = sorted(s)
ans = 0
for i in range(0,n,2):
    if j.index(s[i]) % 2 == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

SA = sorted(A)
ans = 0
for i in range(N):
  if (i + SA.index(A[i])) % 2 == 1:
    ans += 1
print(ans//2)

Submission status: Time Limit Exceeded

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

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

sorted_A = sorted(A)

cnt = 0
for i in range(1, N+1):
    ind = sorted_A.index(A[i])
    if ind % 2 != i % 2:
        cnt += 1

print(cnt // 2)

Submission status: Time Limit Exceeded

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
    ans += 1
    A = sort_once(A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = int(input())
a = []
count = 0
for j in range(s):
        a.append(int(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: Time Limit Exceeded

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
print(c)

Submission status: Time Limit Exceeded

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())
#    print(a)
    while 1:
        flag=0
        for i in range(n-2):
            if a[i]>a[i+2]:
                a[i],a[i+2]=a[i+2],a[i]
                flag=1
        if not flag:
            break
#    print(a)
    ans=0
    while 1:
        flag=0
        for i in range(n-1):
            if a[i]>a[i+1]:
                a[i],a[i+1]=a[i+1],a[i]
                flag=1
                ans+=1
        if not flag:
            break
#    print(a)
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input())for _ in range(n)]
o = a[::2]
e = a[1::2]
o.sort()
e.sort()
l = [0] * n
for i in range(n):
  if i % 2 == 0:
    l[i] = o[i // 2]
  else:
    l[i] = e[(i - 1) // 2]
ans = 0
for _ in range(n):
  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: Time Limit Exceeded

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])
cnt = 0
for k in aa:
    if k not in bb:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

INF = float('inf')


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


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

count = 0
for i in range(N):
    tmp = B.index(A[i])
    diff = abs(i - tmp)
    if diff % 2 == 1:
        count += 1

print(count // 2)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

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


dic = dict()

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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 // 2)

Submission status: Time Limit Exceeded

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

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

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
s = [int(input()) for _ in range(N)]
sa=s.copy()
sa.sort()
x=0
for i in s:
  if s.index(i) %2 !=sa.index(i) %2:
    x+=1
print(math.ceil(x/2))

Submission status: Time Limit Exceeded

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
for j in range(n):
    a[j]=i()
b=[a[j] for j in range(n)]
a.sort()
cnt=0
for j in range(n):
    if b.index(a[j])%2!=j%2:
        cnt+=1


print cnt/2

Submission status: Time Limit Exceeded

Solution code:
def solve(a):
	b = a.copy()
	b.sort()
	l = len(a)
	idx = map(b.index, a)
	cnt = 0
	for i, k in enumerate(idx):
		cnt += (i-k) % 2
	return cnt // 2

n = int(input())
a = [int(input()) for i in range(n)]
print(solve(a))

Submission status: Time Limit Exceeded

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:
	lis2.append(inp[s])
	s+=2
	if s>N-1:
		flag=0
num =len(lis2)
for s in range(num):
	if s!=0:
		if (s+1)%2!=1:
			temp=s+1
		else:	temp=s+2
		if check[temp] not in lis2:
			ans+=1
		continue
	elif s==0:
		if check[s] not in lis2:
			ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding: cp932
N = int(input())
inp =[]
for s in range(N):
	inp.append(int(input()))
odd,even=0,0
check = inp[:]
check.sort()
flag=1
lis,lis2 = [],[]
s=0
while flag==1:
	lis.append(check[s])
	lis2.append(inp[s])
	s+=2
	if s>N-1:
		flag=0
num =len(lis)
ans=0
for s in range(num):
	if lis[s] not in lis2:
		ans+=1
		lis[s] =-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding: cp932
N = int(input())
inp =[]
for s in range(N):
	inp.append(int(input()))
odd,even=0,0
check = inp[:]
check.sort()
#print(check)
#print(inp)
for s in range(len(check)):
	t = check[s]
	rank = inp.index(t)
	cul = (s+1)%2
	rankCul =(rank+1)%2
	if (cul ==1) & (rankCul!=1):
		odd+=1
	if (cul !=1) & (rankCul==1):
		even+=1

#print(odd)
#print(even)
print(max(odd,even))

Submission status: Time Limit Exceeded

Solution code:
#coding: cp932
N = int(input())
inp =[]
for s in range(N):
	inp.append(int(input()))
odd,even=0,0
check = inp[:]
check.sort()
#print(check)
#print(inp)
for s in range(len(check)):
	t = check[s]
	rank = inp.index(t)
	if ((s+1)%2 ==1) & ((rank+1)%2!=1):
		odd+=1
	if ((s+1)%2 !=1) & ((rank+1)%2==1):
		even+=1

#print(odd)
#print(even)
print(max(odd,even))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math,sys
n = input()
a = [input() for i in range(n)]
def bbubbblesort(l):
    cnt = 0
    for index in xrange(len(l)-1, 0, -1):
        flag = 1
        for low in xrange(index-1):
            if l[low] > l[low+2]:
                tmp = l[low+2]
                l[low+2] = l[low]
                l[low] = tmp
                flag = 0
                cnt += 1
        if flag:
            break
    return l
def shaker_sort(buff):
    low = cnt = 0
    high = len(buff) - 1
    j = -1
    while low < high:
        for i in xrange(low, high):
            if buff[i] > buff[i + 1]:
                temp = buff[i]
                buff[i] = buff[i + 1]
                buff[i + 1] = temp
                j = i
                cnt += 1
        high = j
        for i in xrange(high, low, -1):
            if buff[i - 1] > buff[i]:
                temp = buff[i - 1]
                buff[i - 1] = buff[i]
                buff[i] = temp
                j = i
                cnt += 1
        low = j
    return cnt
A = bbubbblesort(a)
print shaker_sort(A)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
	A.append(int(input()))
B = sorted(A)
s = 0
for l in A:
	t = (A.index(l)-B.index(l)) % 2
	s += t
print(t)

Submission status: Time Limit Exceeded

Solution code:
# coding: UTF-8
n = int(raw_input())
pre = []
aft = []
for var in range(n):
    pre.append(int(raw_input()))

for var in range(n):
    aft.append(pre[var])

aft.sort()
oddcount = 0
evencount = 0
for var in range(n):
    index = aft.index(pre[var])
    if index % 2 != var % 2:
        if pre[var] % 2 == 0:
            oddcount = oddcount + 1
        else:
            evencount = evencount + 1
print (evencount+oddcount)/2

Submission status: Time Limit Exceeded

Solution code:
import math,sys
n = input()
a = [input() for i in range(n)]
def bbubbblesort(l):
    for index in xrange(len(l)-1, 0, -1):
        flag = 1
        for low in xrange(index-1):
            if l[low] > l[low+2]:
                tmp = l[low+2]
                l[low+2] = l[low]
                l[low] = tmp
                flag = 0
        if flag:
            break
    return l
def bubblesort(l):
    cnt = 0
    for index in xrange(len(l)-1, 0, -1):
        flag = 1
        for low in xrange(index):
            if l[low] > l[low+1]:
                tmp = l[low+1]
                l[low+1] = l[low]
                l[low] = tmp
                cnt += 1
                flag = 0
        if flag:
            break
    return cnt
A = bbubbblesort(a)
print bubblesort(A)

Submission status: Time Limit Exceeded

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

def three_change(i):
    a[i], a[i + 2] = a[i + 2], a[i]

def two_change(i):
    a[i],a[i + 1] = a[i + 1], a[i]

sorted_a = a[:]
sorted_a = sorted(sorted_a)


tar_ind = n - 1
count = 0
while (tar_ind >= 0):
    target = sorted_a[tar_ind]
    if(target != a[tar_ind]):
        cur_ind = a.index(target)
        tmp = tar_ind - cur_ind
        m2 = tmp // 2
        m1 = tmp % 2
        count += m1
        for i in range(m2):
            three_change(cur_ind)
            cur_ind += 2
        for i in range(m1):
            two_change(cur_ind)
            cur_ind += 1
    tar_ind -= 1

print(count)

Submission status: Time Limit Exceeded

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()
    c[j*2]=a[j]
    b[j]=i()
    c[j*2+1]=b[j]
if n%2==1:
    a[n/2]=i()
    c[n-1]=a[n/2]
a.sort()
b.sort()
c.sort()

for i in range(len(a)):
    cnt+=abs(c.index(a[i])-i*2)

print cnt

Submission status: Time Limit Exceeded

Solution code:
n = input()
a = [input() for i in range(n)]
def bbubbblesort(l):
    for index in xrange(len(l)-1, 0, -1):
        for low in xrange(index-1):
            if l[low] > l[low+2]:
                tmp = l[low+2]
                l[low+2] = l[low]
                l[low] = tmp
    return l
def bubblesort(l):
    cnt = 0
    for index in xrange(len(l)-1, 0, -1):
        for low in xrange(index):
            if l[low] > l[low+1]:
                tmp = l[low+1]
                l[low+1] = l[low]
                l[low] = tmp
                cnt += 1
    return cnt
A = bbubbblesort(a)
print bubblesort(A)

Submission status: Time Limit Exceeded

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

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

l2 = sorted(l1)

s = []

for i in range(n):
	if i % 2 == 1:
		s.append(l1[i])

count = 0

for i in range(n):
	if i % 2 == 1:
		if l2[i] not in s:
			count += 1

print count

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n = int(input())
    a = [0] * n
    indices = {}
    for i in range(n):
        a[i] = int(input())
        indices[a[i]] = i
    b = sorted(a)
    for j in range(n - 1, -1, -1):
        i = indices[b[j]]
        while i + 2 < n and a[i] > a[i + 2]:
            tmp = a[i + 2]
            a[i + 2] = a[i]
            a[i] = tmp
            indices[a[i]] = i
            indices[a[i + 2]] = i + 2
            i += 2
    ans = 0
    for i in range(n - 1):
        if a[i] != b[i]:
            ans += 1
            tmp = a[i + 1]
            a[i + 1] = a[i]
            a[i] = tmp
    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    indices = {}
    for i in range(n):
        indices[a[i]] = i
    b = sorted(a)
    for j in range(n - 1, -1, -1):
        i = indices[b[j]]
        while i + 2 < n and a[i] > a[i + 2]:
            tmp = a[i + 2]
            a[i + 2] = a[i]
            a[i] = tmp
            indices[a[i]] = i
            indices[a[i + 2]] = i + 2
            i += 2
    ans = 0
    for i in range(n - 1):
        if a[i] != b[i]:
            ans += 1
            tmp = a[i + 1]
            a[i + 1] = a[i]
            a[i] = tmp
    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

count=1
while count!=0:
    count=0
    for i in range(N-2):
        if(a[i]>a[i+2]):
            a[i],a[i+2]=a[i+2],a[i]
            count+=1

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
n = int(input())
a = [int(input()) for _ in range(n)]
x = [a[i] for i in range(0, n, 2)]
a.sort()
y = [a[i] for i in range(1, n, 2)]
ans = 0
for it in x:
    if it in y:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getArray(N)
s = sorted(A)
alta = {}
for i in range(N):
    alta[s[i]] = i
A = [alta[i] for i in A]

"""
N <= 100000
O(NlogN)まで
1つとばし交換をたくさん行う
隣接とばしの最小回数は
N = 4
A = [2, 4, 3, 1]の場合最終形は
A = [1, 2, 3, 4]
バブルソートの交換回数
1, 2, 3の自分より左にある自分より大きいものの数

1, 3, 5...番目にあるものは1, 3, 5...番目にしかいけない
いくつ路線を変える必要があるか
"""

def counter(array):
    n = len(array)
    cnt = 0
    for i in range(n):
        if (array[i] % 2) ^ (i % 2):
            cnt += 1
    return cnt

print(counter(A) // 2)