Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n, q = map(int, input().split())

edge = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    edge[a-1].append(b)
    edge[b-1].append(a)

cnt = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x


def dfs(now, bef):
    for nxt in edge[now-1]:
        if nxt != bef:
            cnt[nxt-1] += cnt[now-1]
            dfs(nxt, now)


dfs(1, -1)
print(*cnt)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)


def input(): return sys.stdin.readline()


N, Q = map(int, input().split())
ab = [[] for _ in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)

P = [0 for _ in range(N)]
for i in range(Q):
  p, x = map(int, input().split())
  P[p-1] += x


def dfs(p, par):
  for i in ab[p-1]:
    if i != par:
      P[i-1] += P[p-1]
      dfs(i, p)


dfs(1, -12345)
print(" ".join(map(str, P)))
### BUGGY CODE ###

import sys

input = sys.stdin.readline

X, Y, Z, K = map(int, input().split())
a = map(int, input().split())
b = list(map(int, input().split()))
c = map(int, input().split())

d = (aa + bb for aa in a for bb in b)
d = sorted(d, reverse=True)

e = (cc + dd for cc in c for dd in d[:K])
e = sorted(e, reverse=True)[:K]

print('\n'.join(map(str, e)))

### FIXED CODE ###

# https://www.kumilog.net/entry/python-speed-comp#input-%E3%81%A8-sysstdinreadline
# https://teratail.com/questions/88396

from heapq import heapify, heappush, heappop
import sys

input = sys.stdin.readline


class Data:
    def __init__(self, value, indices):
        self.value = value
        self.indices = indices

    def __lt__(self, other):
        return self.value < other.value


X, Y, Z, K = map(int, input().split())
a = map(int, input().split())
b = map(int, input().split())
c = map(int, input().split())

a = list(sorted(a, reverse=True))
b = list(sorted(b, reverse=True))
c = list(sorted(c, reverse=True))

hq = []
heapify(hq)

t = a[0] + b[0] + c[0]
t *= -1

d = Data(t, (0, 0, 0))

heappush(hq, d)

dtpls = ((1, 0, 0), (0, 1, 0), (0, 0, 1))

st = set()

cnt = 0
for _ in range(K):
    d = heappop(hq)
    print(-d.value)
    for dtpl in dtpls:
        na = d.indices[0] + dtpl[0]
        if na >= X: continue
        nb = d.indices[1] + dtpl[1]
        if nb >= Y: continue
        nc = d.indices[2] + dtpl[2]
        if nc >= Z: continue

        nt = a[na] + b[nb] + c[nc]
        nt *= - 1

        ntpl = (na, nb, nc)
        if ntpl in st: continue
        heappush(hq, Data(nt, ntpl))
        st.add(ntpl)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
p = 10**9 + 7
total = 0
for i in range(60):
    cnt_1, cnt_0 = 0, 0
    for j in range(N):
        if (A[j]>>i)&1:
            cnt_1 += 1
        else:
            cnt_0 += 1
    total += pow(2, i, p) * cnt_0 * cnt_1 %p
print(total%p)

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():

    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    total = 0
    for i in range(60):
        cnt_1, cnt_0 = 0, 0
        for j in range(N):
            if (A[j]>>i)&1:
                cnt_1 += 1
            else:
                cnt_0 += 1
        total += pow(2, i, p) * cnt_0 * cnt_1 %p
    print(total%p)
main()
### BUGGY CODE ###

n = int(input())
D ={}
for i in range(n):
    s = input()
    if s in D.keys(): #sが辞書Dにあるのかチェック(これはある場合)
        D[s] += 1 #D[s] += 1 ->{'s':今までに出てきた回数+1}となる
    else:  #sが辞書Dにない場合
        D[s] = 1 #D[s] = 1 ->{'s':1}となる
poll = [j for j in D if D[j] == max(D.values())]
print('\n'.join(sorted(poll)))

### FIXED CODE ###

n = int(input())
D ={}
for i in range(n):
    s = input()
    if s in D.keys(): #sが辞書Dにあるのかチェック(これはある場合)
        D[s] += 1 #D[s] += 1 ->{'s':今までに出てきた回数+1}となる
    else:  #sが辞書Dにない場合
        D[s] = 1 #D[s] = 1 ->{'s':1}となる
maxD = max(D.values())
poll = [k for k,v in D.items() if v == maxD]
print('\n'.join(sorted(poll)))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

n=100

from fractions import gcd
from functools import reduce
gs = [reduce(gcd, A[100*i:100*(i+1)]) for i in range((N-1)//100 + 1)]

answer = 0

for i in range(N):
  k = i%100
  i = (i//100)
  
  g = reduce(gcd, A[i*100:k] + A[k+1:(i+1)*100] + gs[0:i] + gs[i+1:])

  answer = max(answer, g)

print(answer)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

L = len(A)
from functools import reduce
from fractions import gcd

def lcm(a,b):
  return (a*b)//gcd(a,b)

g = reduce(gcd, A)
l = reduce(lcm, A)

def _gcd(a,b):
  if a is None and b is None:
    return None
  if a is None:
    return b
  if b is None:
    return a
  else:
    return gcd(a,b)

class SegTree():
  import math
  def __init__(self, func, A, identity=1):
    self._func = func
    self._N = 1
    while self._N < len(A):
      self._N *= 2
       # 長さ 7 なら N=3 (2^3=8)
    self._identity = identity # maxなら-1e9, sumなら0, productなら1

    self._tree = [self._identity] * (2*self._N -1) 
    self._tree[self._N-1:self._N-1+ len(A)] = A #最下段に元の配列を
    for i in range(self._N-2, -1, -1):
      self._update_single_node(i)
    ########
    # N=3: #
    # 0000 #
    # 1122 #
    # 3456 #
    ########
    self._node_range = [(i-self._N+1,i-self._N+2) for i in range(2*self._N-1)] #right_exclusive
    for i in range(self._N-2, -1, -1):
      self._node_range[i] = (self._node_range[2*i+1][0], self._node_range[2*i+2][1])

  def _update_single_node(self,i):
    self._tree[i] = self._func(self._tree[2*i+1], self._tree[2*i+2])

  def point_update(self,i,x):
    # A[i] = x (addではないので注意)
    j = self._N-1+i
    self._tree[j] = x
    while j>0:
      j = (j-1)//2
      self._update_single_node(j)

  def range_query(self, l, r, on=0):
    # reduce(func, A[l:r])
    # onはノード[on]上と重なる部分の，ということ
    onl, onr = self._node_range[on]
    
    # ノード[on]上はすべて覆う
    if l<=onl and onr<=r:
      return self._tree[on]
    
    # 重なりなし
    elif onr<=l or r<=onl:
      return self._identity
    
    else:
      return self._func(self.range_query(l, r, on=2*on+1),
                        self.range_query(l, r, on=2*on+2))

st = SegTree(_gcd, A, identity=None)

answer = 0
for i in range(len(A)):
  st.point_update(i, A[i-1])
  answer = max(answer, st._tree[0])
  st.point_update(i, A[i])

print(answer)
### BUGGY CODE ###

from math import floor, ceil
from numpy import array
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
L = array([0 for i in range(N+2)])

for _ in range(K):
    for i, a in enumerate(A):
        l = max(0, ceil(i+1-a-0.5))
        r = min(N+2, floor(i+1+a+0.5)+1)
        L[l:r] += 1
        #for j in range(l, r):
        #   L[j] += 1
    for i in range(N):
        A[i] = L[i+1]
    L = array([0 for i in range(2*N+2)])
    if all([A == N for a in A]):
        break
print(*A)

### FIXED CODE ###

from itertools import accumulate
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

for _ in range(K):
    S = [0] * (N + 1)
    for i, a in enumerate(A):
        l = min(N-1, max(0, i-a))
        r = min(N-1, i+a)
        S[l] += 1
        S[r+1] -= 1
    A = list(accumulate(S))[:-1]
    if all([a == N for a in A]):
        break
print(*A)
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
query = [tuple(list(map(int, input().split())) + [i]) for i in range(Q)]
query_result = [0 for i in range(Q)]

collar_pos = [-1] * (N + 1)
bit = [0] * (N + 1)

def bit_add(index, num):
    while (index <= N):
        bit[index] += num
        index += index & -index
    return

def bit_sum(index):
    result = 0
    while (index > 0):
        result += bit[index]
        index -= index & -index
    return result

sorted_query = sorted(query, key=lambda query: query[1])

index = 1
for query in sorted_query:
    while (index <= query[1]):
        # update BIT
        if (collar_pos[c[index-1]] != -1):
            bit_add(collar_pos[c[index-1]], -1)
        bit_add(index, 1)
        # update collar_pos
        collar_pos[c[index-1]] = index
        index += 1
    query_result[query[2]] = bit_sum(query[1]) - bit_sum(query[0]-1)

for q in query_result:
    print(q)

### FIXED CODE ###

class BinaryIndexedTree(object):
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)

    def bit_add(self, index, num):
        while (index <= self.N):
            self.bit[index] += num
            index += index & -index
        return

    def bit_sum(self,index):
        result = 0
        while (index > 0):
            result += self.bit[index]
            index -= index & -index
        return result

    def bit_sum_range(self, l, r):
        if (l == r):
            return 1
        else:
            return self.bit_sum(r) - self.bit_sum(l - 1)

def main():
    from sys import stdin
    N, Q = list(map(int, input().split()))
    c = list(map(int, input().split()))
    readline = stdin.readline
    query = [list(map(int, readline().split())) + [i] for i in range(Q)]
    query_result = [0 for i in range(Q)]
    collar_pos = [-1] * (N + 1)
    bit = BinaryIndexedTree(N)

    sorted_query = sorted(query, key=lambda query: query[1])

    index = 1
    for query in sorted_query:
        l, r, q = query
        while (index <= r):
            # update BIT
            if (collar_pos[c[index-1]] != -1):
                bit.bit_add(collar_pos[c[index-1]], -1)
            bit.bit_add(index, 1)
            # update collar_pos
            collar_pos[c[index-1]] = index
            index += 1
        query_result[q] = bit.bit_sum_range(l, r)

    print(*query_result, sep='\n')

if __name__ == '__main__':
    main()
### BUGGY CODE ###

a=int(input())
b=[int(i) for i in input().split()]
c=[]
for i in range(a-1):
    for j in range(i+1,a):
        if b[i]==b[j]:
            c.append(1)
            break
if len(c)>0:
    print('NO')
else:
    print('YES')

### FIXED CODE ###

a=int(input())
b=[int(i) for i in input().split()]
c=list(set(b))
if len(b)==len(c):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import math


def main():
    inputs = input().split()
    inputs = [int(i) for i in inputs]

    a = inputs[0]
    b = inputs[1]

    g = gcd(a, b)
    d = {}

    min_n = min([a, b])

    for i in range(2, g + 1):
        while True:
            if g % i == 0:
                g /= i
                d[i] = i
            else:
                break

    print(len(d) + 1)


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import math


def main():
    inputs = input().split()
    inputs = [int(i) for i in inputs]

    a = inputs[0]
    b = inputs[1]

    g = n = gcd(a, b)
    d = {}

    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i:
            continue
        d[i] = i
        while n % i == 0:
            n /= i

    if n != 1:
        d[n] = n

    print(len(d) + 1)


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,M = map(int,input().split())
AB = []
for m in range(M):
    AB.append([int(i)-1 for i in input().split()])
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf = UnionFind(N)
for ab in AB:
    uf.union(ab[0],ab[1])
group_dict = uf.all_group_members()
ans = 0
for key in group_dict.keys():
    ans = max(ans,len(group_dict[key]))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
N,M = map(int,input().split())
uf = UnionFind(N)
for m in range(M):
    temp = [int(i)-1 for i in input().split()]
    uf.union(temp[0],temp[1])
print(-min(uf.parents))
### BUGGY CODE ###

import time

n, m, k = map(int, input().split())

friends = [[] for i in range(n)]
cands = [None for i in range(n)]
cycles = []
visited = [False for i in range(n)]
count = [0 for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].append(b)
    friends[b].append(a)

def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    cycle.append(x)
    for i in friends[x]:
        dfs(i)
    return

time.sleep(3)

for i, v in enumerate(visited):
    if v:
        continue
    cycle = []
    dfs(i)
    l = len(cycle)
    ind = len(cycles)
    cycles.append(cycle)
    for fr in cycle:
        cands[fr] = ind
        count[fr] = l - 1 - len(friends[fr])


for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    if a in cycles[cands[b]]:
        count[a] -= 1
        count[b] -= 1

for i in count:
    print(i, end=" ")

### FIXED CODE ###

import time, sys
sys.setrecursionlimit(int(1e7))

n, m, k = map(int, input().split())

friends = [[] for i in range(n)]
cands = [None for i in range(n)]
cycles = []
visited = [False for i in range(n)]
count = [0 for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].append(b)
    friends[b].append(a)

def dfs(x):
    visited[x] = True
    cycle.add(x)
    for i in friends[x]:
        if not visited[i]:
            dfs(i)
    return


for i, v in enumerate(visited):
    if v:
        continue
    cycle = set()
    dfs(i)
    l = len(cycle)
    ind = len(cycles)
    cycles.append(cycle)
    for fr in cycle:
        cands[fr] = ind
        count[fr] = l - 1 - len(friends[fr])


for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    if a in cycles[cands[b]]:
        count[a] -= 1
        count[b] -= 1

for i in count:
    print(i, end=" ")
### BUGGY CODE ###

import math

k = int(input())

wa = 0

for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            wa += math.gcd(math.gcd(a,b),c)


print(wa)

### FIXED CODE ###

import math
from functools import reduce
import sys
sys.setrecursionlimit(2000000)

k = int(input())

wa = 0

for a in range(1,k+1):
    for b in range(a+1,k+1):
        for c in range(b+1,k+1):
            li = [a,b,c]
            wa += reduce(math.gcd,li)*6

for a in range(1,k+1):
    for b in range(a+1,k+1):
        wa += math.gcd(a,b)*6

for a in range(1,k+1):
    wa += a
    

print(wa)
### BUGGY CODE ###

import itertools as ite
n, m = map(int, input().split())
L = [list(map(int,input().split())) for i in range(n)]
L2= ite.permutations(L, n)
max_money = 0
for ele in L2:
    d = 0
    money = 0
    for ele2 in ele:
        if ele2[0]+d <=m:
            money +=ele2[1]
        d+=1
    if max_money < money:
        max_money = money
print(max_money)

### FIXED CODE ###

import sys
from collections import defaultdict
import heapq
input = sys.stdin.readline
n, limit = map(int, input().split())
dic = defaultdict(list)

for _ in range(n):
    a, b = map(int, input().split())
    dic[a].append(b)

L = []
ans = 0
for i in range(limit+1):
    for val in dic[i]:
        heapq.heappush(L, -val)
    if len(L):
        ans -= heapq.heappop(L)
print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())

S = np.array([], dtype="U10")
cnt = np.array([], dtype=int)

for i in range(N):
  s = input()
  if s in S:
    cnt[np.where(S==s)] += 1
  else:
    idx = np.searchsorted(S,s)
    S = np.insert(S,idx,s)
    cnt = np.insert(cnt,idx,1)

ans = S[cnt==cnt.max()]

for s in ans:
  print(s)

### FIXED CODE ###

N = int(input())

d = {}
for i in range(N):
  s = input()
  if s in d.keys():
    d[s] += 1
  else:
    d[s] = 1

M = max(d.values())
for j,k in sorted(d.items()):
  if k == M:
    print(j)
### BUGGY CODE ###

N, X, Y = map( int, input().split(" "))

dlist = []
for i in range(1,N+1):
  for j in range(i,N+1):
    dis = min( abs(j-i), abs(X-i) +1+abs(j-Y), abs(Y-i) +1+abs(j-X) )
    dlist.append(dis)
    
for i in range(1,N):
  cnt = 0
  for val in dlist:
    if( val == i ):
      cnt+=1
  print( cnt )


### FIXED CODE ###

N, X, Y = map( int, input().split(" "))

ans = [0]*N
for i in range(1,N+1):
  for j in range(i,N+1):
    dis = min( abs(j-i), abs(X-i) +1+abs(j-Y), abs(Y-i) +1+abs(j-X) )
    ans[dis]+=1
    
for i in range(1,N):
  print( ans[i] )
### BUGGY CODE ###

N = int(input())
l = list(map(int, input().split()))
ans = []

if N % 2 == 0:
    flag = 0
else:
    flag = 1

for ix,i in enumerate(l):
    if ix % 2 == flag:
        ans.append(i)
    else:
        ans.insert(0, i)
    
print(" ".join(map(str, ans)))

### FIXED CODE ###

n = int(input())
a = list(map(str,input().split()))
b = a[::-1]
b = b[::2]

if n%2 == 0:
  c = a[::2]
else:
  c = a[1::2]
d = b+c

if n >= 2:
  print(' '.join(d))
else:
  print(a[0])
### BUGGY CODE ###

n,m=map(int,input().split())
p=list(map(int,input().split()))
rank=[0 for i in range(n)]
r=[i for i in range(n)]
sp=[{p[i]-1} for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    if rank[rx]>rank[ry]:
      r[ry]=rx
      sp[rx]=sp[rx]|sp[ry]
    elif rank[rx]<rank[ry]:
      r[rx]=ry
      sp[ry]=sp[rx]|sp[ry]
    else:
      r[rx]=ry
      sp[ry]=sp[rx]|sp[ry]
      rank[rx]+=1
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def get(x):
  return sp[root(x)]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if (i in get(i)) or i+1==p[i]:
    ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
p=list(map(int,input().split()))
r=[i for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    r[rx]=ry
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if root(i)==root(p[i]-1) or i+1==p[i]:
    ans+=1
print(ans)
### BUGGY CODE ###

s = input()

a = [0] * len(s)
b = [0] * len(s)
c = [0] * len(s)
q = 0

if s[0] == "A":
    a[0] = 1
elif s[0] == "?":
    a[0] = 1
    q = 1

for i in range(1, len(s)):
    if s[i] == "A":
        a[i] = a[i - 1] + 3**q
        b[i] = b[i - 1]
        c[i] = c[i - 1]
    elif s[i] == "B":
        a[i] = a[i - 1]
        b[i] = b[i - 1] + a[i - 1]
        c[i] = c[i - 1]
    elif s[i] == "C":
        a[i] = a[i - 1]
        b[i] = b[i - 1]
        c[i] = c[i - 1] + b[i - 1]
    else:
        a[i] = 3 * a[i - 1] + 3**q
        b[i] = 3 * b[i - 1] + a[i - 1]
        c[i] = 3 * c[i - 1] + b[i - 1]
        q += 1
        
print(c[len(s) - 1] % (10**9 + 7))

### FIXED CODE ###

s = input()

a = [0] * len(s)
b = [0] * len(s)
c = [0] * len(s)
q = 0
m = 10**9 + 7

if s[0] == "A":
    a[0] = 1
elif s[0] == "?":
    a[0] = 1
    q = 1

for i in range(1, len(s)):
    if s[i] == "A":
        a[i] = (a[i - 1] + pow(3, q, m)) % m
        b[i] = b[i - 1] % m
        c[i] = c[i - 1] % m
    elif s[i] == "B":
        a[i] = a[i - 1] % m
        b[i] = (b[i - 1] + a[i - 1]) % m
        c[i] = c[i - 1] % m
    elif s[i] == "C":
        a[i] = a[i - 1] % m
        b[i] = b[i - 1] % m
        c[i] = (c[i - 1] + b[i - 1]) % m
    else:
        a[i] = (3 * a[i - 1] + pow(3, q, m)) % m
        b[i] = (3 * b[i - 1] + a[i - 1]) % m
        c[i] = (3 * c[i - 1] + b[i - 1]) % m
        q += 1
        
print(c[len(s) - 1] % m)
### BUGGY CODE ###

from scipy.misc import comb

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    l = a[i]
    a[i] = ''
    ans = 0
    a_s = set(a)
    for j in a_s:
        c = a.count(j)
        ans += comb(c,2,exact=True)
    print(ans)
    a[i] = l

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))

c = Counter(a)
key = c.keys()
comb = 0
for i in key:
    comb += (c[i]) * (c[i]-1) // 2

for i in a:
    ans = comb - (c[i]-1)
    print(ans)
### BUGGY 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)


### FIXED CODE ###

import math

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

"""
ソート後の位置までの距離が奇数だと操作１が一回必要になる
一度の操作１で最大で２個までのソート後の位置までの距離が奇数のものを偶数にずらしてあげられる
ので、正しい位置までの距離が奇数のものの個数をしらべて、最小の操作１の回数を求める
"""
cnt = 0
for i in range(N):
    if abs(i - idx_A[B[i]]) % 2 == 0: # あまり０なら操作２だけで所定の位置に動かせる
        continue
    else:
        cnt += 1


print(math.ceil(cnt/2))
### BUGGY CODE ###

N = int(input())

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

total = a[0]

for i in range(1,N):
    total *= a[i]
    if  10 ** 18 < total and 0 not in a:
        print(-1)
        exit()
print(total)


### FIXED CODE ###

N = int(input())

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

a.sort()

if a[0] == 0:
    print(0)
    exit()

total = a[0]

for i in range(1,N):
    total *= a[i]
    if  10 ** 18 < total:
        print(-1)
        exit()
print(total)
### BUGGY CODE ###

N=int(input())
uvw=[list(map(int, input().split())) for i in range(N-1)]
mat=[[0]*(N+1) for i in range(N+1)]
nodelink=[[] for i in range(N+1)]
for i in range(N-1):
  mat[uvw[i][0]][uvw[i][1]]=uvw[i][2]
  mat[uvw[i][1]][uvw[i][0]]=uvw[i][2]
  nodelink[uvw[i][0]].append(uvw[i][1])
  nodelink[uvw[i][1]].append(uvw[i][0])
  
color=[-1]*(N+1)

def f(nuru, iro):
  color[nuru]=iro
  tonari=nodelink[nuru]
  for nuruyo in tonari:
    if color[nuruyo]<0:
      if (mat[nuru][nuruyo]%2)==0:
        f(nuruyo, iro)
      else:
        f(nuruyo, 1-iro)
      
f(1, 0)

for i in range(1, N+1):
  print(color[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5+1)

N=int(input())
uvw=[list(map(int, input().split())) for i in range(N-1)]
nodelink=[[] for i in range(N+1)]
for i in range(N-1):
  nodelink[uvw[i][0]].append([uvw[i][1], uvw[i][2]])
  nodelink[uvw[i][1]].append([uvw[i][0], uvw[i][2]])
  
color=[-1]*(N+1)

def f(nuru, iro):
  color[nuru]=iro
  tonari=nodelink[nuru]
  for nuruyo in tonari:
    if color[nuruyo[0]]<0:
      if (nuruyo[1]%2)==0:
        f(nuruyo[0], iro)
      else:
        f(nuruyo[0], 1-iro)
      
f(1, 0)

for i in range(1, N+1):
  print(color[i])