Harryxun/stf_run huggingface dataset:
import sys
import numpy as np
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N = ir()
    c = lr()
    ab = [[] for i in range(N)]
    for i in range(N-1):
        a, b = lr()
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    tot = N*(N+1)//2
    cnt = np.zeros((N, N), np.int32)
    vis = [0]*N
    row = np.arange(N).astype(np.int32)
    col = np.zeros(N, np.int8)
    s = [[0, col]]
    vis[0] += 1
    while len(s) > 0:
        v, col = s.pop()
        cnt[row, col] += 1
        cnt[c[v]-1, col[c[v]-1]] -= 1
        for i in ab[v]:
            if vis[i] == 0:
                col[c[v]-1] += 1
                s.append([i, col.copy()])
                vis[i] += 1
    print(*(tot-np.sum(cnt*(cnt+1)//2, axis=1)).tolist(), sep='\n')
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
sys.setrecursionlimit(10**6)
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & (-i)
def resolve():
    N = ir()
    c = lr()
    ab = [[] for i in range(N)]
    for i in range(N-1):
        a, b = lr()
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    tot = N*(N+1)//2
    il = [0]*N
    ol = [0]*N
    cnt = [0]
    def dfs(u, p):
        cnt[0] += 1
        il[u] = cnt[0]
        for i in ab[u]:
            if i != p:
                dfs(i, u)
        ol[u] = cnt[0]
    dfs(0, -1)
    vs = [[] for i in range(N)]
    for i in range(N):
        vs[c[i]-1].append(i)
    sl = Bit(N)
    for i in range(1, N+1):
        sl.add(i, 1)
    for i in range(N):
        his = []
        ans = tot
        tvs = sorted(vs[i], key=lambda x: il[x])[::-1]
        for v in tvs:
            n = 1
            for j in ab[v]:
                if il[j] > il[v]:
                    tmp = sl.sum(ol[j])-sl.sum(il[j]-1)
                    ans -= tmp*(tmp+1)//2
                    n += tmp
            sl.add(il[v], -n)
            his.append([il[v], n])
        tmp = sl.sum(ol[0])-sl.sum(0)
        ans -= tmp*(tmp+1)//2
        for h in his:
            sl.add(h[0], h[1])
        print(ans)
resolve()
a,b,c=(int(i) for i in input().split())
for i in range(1,10):
  c=int(a*c-b)
  print(c)


### FIXED CODE ###

a,b=(int(i) for i in input().split())
if a<=5:
  print(0)
elif 5<a<=12:
  print(b//2)
else:
  print(b)
n=int(input())
l = [*map(int, input().split())]
res = 0
for i in range(1,n-1):
  if l[i-1]<l[i] and l[i]<l[i+1] or l[i-1]>l[i]andl[i]>l[i+1]: res+=1
print(res)

### FIXED CODE ###

n=int(input())
l = list(map(int, input().split()))
res = 0
for i in range(1,n-1):
  if l[i-1]<l[i] and l[i]<l[i+1] or l[i-1]>l[i] and l[i]>l[i+1]: res+=1
print(res)
money = [300000, 200000, 100000]
X, Y = map(int, input().split())
X -= 1; Y -= 1
ans = money[X] + money[Y]
if X + Y:
    print(ans)
else:
    print(ans + 400000)

### FIXED CODE ###

X, Y = map(int, input().split())
syoukin = [3*10**5, 2*10**5, 1*10**5]
if X == 1 and Y == 1:
    print(10*10**5)
else:
    money = 0
    if X <= 3:
        money += syoukin[X-1]
    if Y <= 3:
        money += syoukin[Y-1]
    print(money)
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()] 
if a[0]!=0:
    print ("0")
else:
    a = Counter(a)
    ans = 1
    for i in range(1,len(a)):   
        print(a[i])
        ans*=a[i]**a[i+1]
    print(ans)


### FIXED CODE ###

import collections
n = int(input())
d = list(map(int, input().split()))
mod = 998244353
f = collections.Counter(d)
# print(f)
if d[0] != 0 or f[0] != 1:  # 0は一個だけ
    print(0)
    exit()
ans = 1
box = 1  # 値自体の個数を保存
maxd = max(d)

for i in range(maxd+1):
    ans = ans*box**f[i]
    ans %= mod
    box = f[i]
print(ans)
if s == "RRR":
  print(3)
elif s == "RRS" or s == "SRR":
  print(2)
elif s == "RSR" or s == "RSS" or s == "SSR" or s == "SRS":
  print(1)
else:
  print(0)

### FIXED CODE ###

s = str(input())
if s == "RRR":
  print(3)
elif s == "RRS" or s == "SRR":
  print(2)
elif s == "RSR" or s == "RSS" or s == "SSR" or s == "SRS":
  print(1)
else:
  print(0)
import os, sys, re, math

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

def common_gcd(ex_idx):
    ret = 0
    for i in range(N):
        if i != ex_idx:
            if ret == 0:
                ret = A[i]
            else:
                ret = math.gcd(ret, A[i])
    return ret

ret = 1
for j in range(N):
    ret = max(ret, common_gcd(j))

print(ret)


### FIXED CODE ###

import os, sys, re, math, fractions

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

memo_L = [1] * N
memo_R = [1] * N

for i in range(N):
    if i == 0:
        memo_L[i] = A[i]
        memo_R[i] = A[N-1]
    elif i == N - 1:
        memo_L[i] = fractions.gcd(A[i], memo_L[i-1])
        memo_R[i] = fractions.gcd(A[0], memo_R[i-1])
    else:
        memo_L[i] = fractions.gcd(A[i], memo_L[i-1])
        memo_R[i] = fractions.gcd(A[N-1-i], memo_R[i-1])

memo_R.reverse()

ret = 1
for j in range(N):
    if j == 0:
        ret = max(ret, memo_R[1])
    elif j == N-1:
        ret = max(ret, memo_L[j-1])
    else:
        common_gcd = fractions.gcd(memo_L[j-1], memo_R[j+1])
        ret = max(ret, common_gcd)

print(ret)
import sys

while 1:
  try:
    a, b, c, d, e, f = map(int, raw_input().split())
    g = b / e
    x = (c - g * f) / (float(a) - g)
    y = (c - a * x) / float(b)
    print str(x) + " " + str(y)
  exception: EOFError
    sys.exit()

### FIXED CODE ###

while 1:
    try:
        a, b, c, d, e, f = map(float, raw_input().split())
        x = (c * e - b * f) / (a * e - b * d)
        y = (f * a - c * d) / (a * e - d * b)
        if x == -0.000:
            x = 0.000
        if y == -0.000:
            y = 0.000
        print str('%.3f' % x) + " " + str('%.3f' % y)
    except:
        break
l = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    dx = a * (l[i+1] - l[i])
    if b < dx:
        ans += b
    else:
        ans += dx
print(ans)

### FIXED CODE ###

n, a, b= map(int, input().split())
l = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    dx = a * (l[i+1] - l[i])
    if b < dx:
        ans += b
    else:
        ans += dx
print(ans)
from collections import defaultdict
N = int(input())
C = defaultdict(int)
for i in range(N):
  D = int(input())
  C[D] = i + 1
E = []
H = [1] * (N + 1)
DD = sorted([[k, v] for k, v in C.items()], reverse=True)
Adj = [[] for i in range(N)]
for D, n in DD[:-1]:
  try:
    p = C[D - N + 2 * H[n]]
    if n == p:
      raise Error
    E.append([n, p])
    Adj[n - 1].append(p - 1)
    Adj[p - 1].append(n - 1)
    H[p] += H[n]
  except:
    print(-1)
    break
else:
  dist = [N] * N
  dist[DD[-1][1] - 1] = 0
  Q = [DD[-1][1] - 1]
  for i in range(N - 1):
    s = Q[i]
    for adj in Adj[s]:
      if dist[adj] == N:
        dist[adj] = dist[s] + 1
        Q.append(adj)
  if sum(dist) == DD[-1][0]:
    for e in E:
      print(e[0], e[1])
  else:
    print(-1)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
C = defaultdict(int)
for i in range(N):
  D = int(input())
  C[D] = i + 1
E = []
H = [1] * (N + 1)
DD = sorted([[k, v] for k, v in C.items()], reverse=True)
Adj = [[] for i in range(N)]
for D, n in DD[:-1]:
  try:
    p = C[D - N + 2 * H[n]]
    if n == p:
      raise Error
    E.append([n, p])
    Adj[n - 1].append(p - 1)
    Adj[p - 1].append(n - 1)
    H[p] += H[n]
  except:
    print(-1)
    break
else:
  dist = [N] * N
  dist[DD[-1][1] - 1] = 0
  Q = [DD[-1][1] - 1] + [N] * N
  tail = 1
  for i in range(N):
    s = Q[i]
    if s == N:
      print(-1)
      break
    for adj in Adj[s]:
      if dist[adj] == N:
        dist[adj] = dist[s] + 1
        Q[tail] = adj
        tail += 1
  else:
    if sum(dist) == DD[-1][0]:
      for e in E:
        print(e[0], e[1])
    else:
      print(-1)
import numpy as np

n,m = input().split(" ")
n = int(n)
m = int(m)

H = input().split(" ")
H = np.array([int(h) for h in H])

M = np.zeros((n,n))
for i in range(m):
    a, b = input().split(" ")
    M[int(a)-1, int(b)-1] = 1
    M[int(b)-1, int(a)-1] = 1

G = []
for i in range(n):
    # no path
    if sum(M[i,:])==0:
        G += [i]
    else:
        connected = np.where(M[i, :]==1)[0]
        if (np.max(H[connected]) < H[i]):
            G+= [i]

print(len(G))


### FIXED CODE ###

import numpy as np
 
n,m = input().split(" ")
n = int(n)
m = int(m)
 
H = input().split(" ")
H = np.array([int(h) for h in H])
Hs = np.zeros(n)

for i in range(m):
    a, b = input().split(" ")
    a = int(a) - 1
    b = int(b) - 1
    Hs[a] = np.max([Hs[a], H[b]])
    Hs[b] = np.max([Hs[b], H[a]])
 
G = []
for i in range(n):
    if Hs[i] < H[i]:
        G += [i]
 
print(len(G))
n, m = map(int, input().split())
a = list(map(int, input().split()))
num = sum(a)
cnt = 0
for i in range(n):
    if a[i] < num/(4*m):
        continue
    else:
        cnt += 1
if cnt >= m:
    print("Yes")
else:
    print("No")   

### FIXED CODE ###

n, k = map(int, input().split())
print(min(n%k, k-n%k))
a, b, t = map(int, input().split())
return (t % a) * b

### FIXED CODE ###

a, b, t = map(int, input().split(' '))

print(b * (t // a))
n, m = map(int,input().split())
a = [-1]
for i in range(m):
    ai = int(input())
    a.append(ai)
a.append(n+1)

def factorial(x):
  if x == 0:
    return 1
  else:
    return x * factorial(x-1)

def C(x,y):
    return factorial(x)//(factorial(x-y)*factorial(y))

def f(x):
    if x == 0:
        return 1
    else:
        ret = 0
        for i in range(x//2+1):
            ret += C(x-i,i)
        return ret

b = []
for i in range(m+1):
    b.append(a[i+1]-a[i]-2)

ans = 1
if -1 in b:
    print(0)
else:
    for i in b:
        ans *= f(i)
        ans %= 1000000007
    print(ans%1000000007)

### FIXED CODE ###

n, m = map(int,input().split())
dp = [1]*(n+1)
a = []
for i in range(m):
    ai = int(input())
    a.append(ai)

for i in a:
    dp[i] = 0

for i in range(2,n+1):
    if dp[i] != 0:
        dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)

print(dp[n])
S, T = input().split()
A , B = input().split()

if S == 'blue' or S=='red':
	print(A-1)
else:
	print(B-1)

### FIXED CODE ###

S, T = input().split()
A, B = map(int, input().split())
U = input()
if U == S:    A -= 1
else: B -= 1
print(A, B)
import sys
n, m = map(int, input().split())
x = list(map(int, input().split()))
a = []

if m == 1:
    print(0)
    sys.exit()

#x.sort()
list.sort(x)
#print(x)

for i in range(1, m):
    a.append(x[i] - x[i-1])

list.sort(a, reverse=True)
#print(a)

count = max(x) - min(x)
for i in range(n-1):
    count -= a[i]

print(count)


### FIXED CODE ###

import sys
n, m = map(int, input().split())
x = list(map(int, input().split()))
a = []

if m == 1:
    print(0)
    sys.exit()

#x.sort()
list.sort(x)
#print(x)

for i in range(1, m):
    a.append(x[i] - x[i-1])

#list.sort(a, reverse=True)
a.sort()
#print(a)

count = max(x) - min(x)
for i in range(n-1):
    if len(a) == 0:
        break
    a.pop()
#    count -= a[i]

#print(count)
print(sum(a))
A,B,K = map(int,input().split())

for i in range(K):
  if A > 0:
    A -= 1
  else:
    if B > 0
    B -= 1

print(str(A) + " " + STR(B))

### FIXED CODE ###

A,B,K = map(int,input().split())
 
if K >= A:
  B = B -(K-A)
  A = 0
  if B < 0:
    B = 0
else:
  A = A - K

print(str(A) + " " + str(B))
n = int(input())

t_score = 0
h_score = 0


for i in range(n):
 t, h = input().split()
 if len(t) >= len(h):
  for j in range(len(h)):
   if ord(t[j]) > ord(h[j]):
    t_score += 3
    break
   elif ord(t[j]) < ord(h[j]):
    h_score += 3
    break
  else:
   t_score += 1
   h_score += 1
 elif len(t) < len(h):
   for j in range(len(h)):
    if ord(t[j]) > ord(h[j]):
     t_score += 3
     break
    elif ord(t[j]) < ord(h[j]):
     h_score += 3
     break
   else:
    t_score += 1
    h_score += 1
   
print("{0} {1}".format(t_score, h_score))

### FIXED CODE ###

n = int(input())

t_score = 0
h_score = 0


for i in range(n):
 t, h = input().split()
 if t == h:
  t_score += 1
  h_score += 1
  continue
 if len(t) >= len(h):
  for j in range(len(h)):
   if ord(t[j]) > ord(h[j]):
    t_score += 3
    break
   elif ord(t[j]) < ord(h[j]):
    h_score += 3
    break
  else:
   t_score += 3
 elif len(t) < len(h):
   for j in range(len(t)):
    if ord(t[j]) > ord(h[j]):
     t_score += 3
     break
    elif ord(t[j]) < ord(h[j]):
     h_score += 3
     break
   else:
    h_score += 3

   
print("{0} {1}".format(t_score, h_score))
def main():
    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-1)
        ab[b-1].append(a-1)
    visit=[False]*n
    cnt=[0]*n
    for i in range(q):
        p,x=map(int,input().split())
        cnt[p-1]+=x

    def solve(s,x):
        visit[s]=True
        cnt[s]+=x
        x=cnt[s]
        for i in ab[s]:
            if visit[i]:
                continue
            solve(i,x)
        return
    
    solve(0,0)
    print(*cnt, sep=' ')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline

def main():
    n,q=map(int,input().split())
    t=[[] for _ in range(n+1)]
    cnt=[0]*(n+1)
    tf=[0]*(n+1)
    for i in range(n-1):
        a,b=map(int,input().split())
        t[a].append(b)
        t[b].append(a)
    for i in range(q):
        p,x=map(int,input().split())
        cnt[p]+=x
    d=deque()
    d.append(1)
    tf[1]=1
    while d:
        chk=d.popleft()
        for i in t[chk]:
            if tf[i]==1:
                continue
            else:
                d.append(i)
                tf[i]=1
                cnt[i]+=cnt[chk]
    print(' '.join(map(str,cnt[1:])))

if __name__ == '__main__':
    main()
N = int(input())
array=[int(n) for n in input().split()]

lst=0
for i in range(N+1):
    left_array=array[:N+i]
    print(left_array)
    l = sorted(left_array)[-N:]
    print('l:',l)
    right_array=array[-int(N)+i-3:]
    print(right_array)
    r = sorted(right_array)[:N]
    print('r:',r)
    ans = sum(l)-sum(r)
    print(ans)
    if ans > lst:
        lst= ans
print(lst)

### FIXED CODE ###

N = int(input())
array = [int(n) for n in input().split()]
import copy
import heapq
lst = [None for i in range(N + 1)]
left_lst = copy.deepcopy(lst)
right_lst = copy.deepcopy(lst)
left_array = array[:N]
right_array= [-n for n in array[-N:]]
l_sum = sum(left_array)
r_sum = sum(right_array)
heapq.heapify(left_array)
heapq.heapify(right_array)
left_lst[0] = l_sum
right_lst[0] = r_sum

for k in range(N, 2 * N):
    new_a, new_b = array[k], array[-k - 1]*-1
    heapq.heappush(left_array,new_a)
    heapq.heappush(right_array,new_b)
    old_a = heapq.heappop(left_array)
    l_sum += (new_a - old_a)
    left_lst[k - N + 1] = l_sum
    old_b = heapq.heappop(right_array)
    r_sum += (new_b - old_b)
    right_lst[k - N + 1] = r_sum
lst = [ a + b for a, b in zip(left_lst, list(reversed(right_lst)))]
print(max(lst))
s=input()
res=0
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
        print(list(s[i:j]))
        if set(list(s[i:j]))|{'A','G','C','T'}=={'A','G','C','T'}:
            cnt=len(s[i:j])
        if res<cnt:
            res=cnt

print(res)

### FIXED CODE ###

s=input()

res=0
for i in range(len(s)+1):
    for j in range(i+1,len(s)+1):
        cnt=0
        for x in s[i:j]:
            if x not in ['A','G','C','T']:
                break
            cnt+=1
        if res<cnt:
            res=cnt

print(res)
s = input()
t = input()
def check(a, b):
  if a == '?':
    return True
  else:
    return a == b
  
cand = []
for i in range(len(s)-len(t)+1):
  flag = True
  c = list(s)
  for j in range(len(t)):
    if not check(s[i+j], t[j]):
      flag = False
      break
    c[i+j] = t[j]
  if flag:
    s = ''.join(c)
    cand(s.replace('?', 'a'))
if len(cand):
  cand.sort()
  print(cand[0])
else:
  print("UNRESTORABLE")
    


### FIXED CODE ###

s = input()
t = input()
def check(a, b):
  if a == '?':
    return True
  else:
    return a == b
  
cand = []
for i in range(len(s)-len(t)+1):
  flag = True
  c = list(s)
  for j in range(len(t)):
    if not check(s[i+j], t[j]):
      flag = False
      break
    c[i+j] = t[j]
  if flag:
    cs = ''.join(c)
    cand.append(cs.replace('?', 'a'))
if len(cand):
  cand.sort()
  print(cand[0])
else:
  print("UNRESTORABLE")
import bisect

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

ans = [A[0]]
for i in range(1, N):
    index = bisect.bisect_left(ans, A[i])
    if index > 0:
        ans[index - 1] = A[i]
    else:
        ans = [A[i]] + ans

print(len(ans))


### FIXED CODE ###

r = int(input())
print(3 * r ** 2)
n,t=map(int,input().split())
ct=[list(map(int,input().split())) for _ in range(n)]
mc=100000
for i in range(n):
    if ct[i][1]<=t:
        if ct[i][0]<mc:
            mc=ct[i][0]
if mi==-1:
    print("TLE")
else:
    print(mc)

### FIXED CODE ###

n,t=map(int,input().split())
ct=[list(map(int,input().split())) for _ in range(n)]
mc=100000
for i in range(n):
    if ct[i][1]<=t:
        if ct[i][0]<mc:
            mc=ct[i][0]
if mc==100000:
    print("TLE")
else:
    print(mc)
a,b,x=map(int,input().split())
if a*10**9+b*10<=x:
  print(1000000000)
else:
  n=0
  for i in reversed(range(1,10)):
    max=(x-b*i)//a
    if len(str(max))==i:
      n=max
      break
    elif 10**(i-1)<=max<10**i:
      n=max
      break
  print(n)

### FIXED CODE ###

s=input()
week=['SUN','MON','TUE','WED','THU','FRI','SAT']
print(7-week.index(s))
s = input()
AKB = "KIHBR"
tmp = 0
count = 0
for i in range(len(s)):
  if s[i] == "A" and count < 4:
    count += 1
  elif s[i] == AKB[tmp]:
    tmp += 1

if count <= 4 and tmp == 5:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

s = input()
rep = s.replace("A","")

if rep == "KIHBR" and "AA" not in s and "KIH" in s :
  print("YES")
else:
  print("NO")
#import sys
#sys.setrecursionlimit(1000000)

def findSumOfDigits(n):
    sum = 0
    while n > 0.1:
        sum = sum + (n % 10)
        #print(n % 10)
        n = n - (n % 10)
        n = n / 10
    return sum

# 整数の入力
n = input()
n = int(n)

a = input()
a = int(a)

b = input()
b = int(b)

ans = 0

for i in range(1,n+1):
    #print(i)
    test = findSumOfDigits(i)
    if a <= test <= b:
        ans = ans + i

print(int(ans))


### FIXED CODE ###


# スペース区切りの整数の入力
a, b, c, d = map(int, input().split())

if a+b > c+d:
    print('Left')
elif a+b < c+d:
    print('Right')
else:
    print('Balanced')
a,b = map(int,raw_input().split())
sum=1
for i in range(a,b+1):
    sum*=i
if(sum>0):
    print("Positive")
elif(sum==0):
    print("Zero")
else:
    print("Negative")


### FIXED CODE ###

a,b = map(int,raw_input().split())

if((a<0 and b>0) or a==0 or b==0):
    print("Zero")
elif(a>0):
    print("Positive")
else:
    if((((a-b)*-1)+1)%2==1):
        print("Negative")
    else:
        print("Positive")
x,n = map(int,input().split())
lst = list(map(int,input().split()))
ans = lst[0]

for e in lst:
  if abs(e-n) < abs(e-ans):
    ans = e
   
  elif abs(e-n) == abs(e-ans):
    ans = min(e,ans)
    
  else:
    pass
  
print(ans)

### FIXED CODE ###

x,n = map(int,input().split())
lst = sorted(list(map(int,input().split())))

ans = x
if ans in lst:
    pass
else:
    print(ans)
    exit()

left,right = ans-1,ans+1

while True:
    if left in lst and right in lst:
        left -=1
        right += 1

    elif left in lst:
        print(right)
        exit()

    else:
        print(left)
        exit()
import collections
n = int(input())
s = list(input())
a = collections.Counter(s)
a = list(a.items())
ans = 0
# ar = []
# for i in range(1,2000):
#     c_ar = []
#     for j in range(1,n+1,i):
#         c_ar.append(j)
#     if len(c_ar) >= 3:
#         ar.append(c_ar)
# print(ar)
# print(len(ar))
# for i in range(len(ar)):
#     print(ar[i])
#     print(len(ar[i]))
#     for j in range(len(ar[i])-2):
#         print(s[ar[i][j]-1],s[ar[i][j+1]-1],s[ar[i][j+2]-1])
#         print(ar[i][j]-1, ar[i][j+1]-1, ar[i][j+2]-1)
#         if s[ar[i][j]-1] != s[ar[i][j+1]-1] and s[ar[i][j+1]-1] != s[ar[i][j+2]-1] and s[ar[i][j+2]-1] != s[ar[i][j]-1]:
#             cnt += 1
#             print("Y")
#     print(cnt)
# print(a[0][1],a[1][1],a[2][1])
# print(a[0][1]*a[1][1]*a[2][1]-cnt)
if n == 1 or n == 2 or n == 3:
    print(0)
    exit()
for i in range(1,n//2+3):
    cnt = 0
    #print(i)
    for j in range(n):
        if cnt + 2*i > n-1:
            break
        x,y,z = s[cnt], s[cnt+i], s[cnt+2*i]
        #print(cnt, cnt+i, cnt+i+i)
        if x != y and y != z and z != x:
            ans += 1
        cnt += 1
print(a[0][1]*a[1][1]*a[2][1]-ans)



### FIXED CODE ###

import collections
n = int(input())
s = list(input())
a = collections.Counter(s)
a = list(a.items())
ans = 0
# ar = []
# for i in range(1,2000):
#     c_ar = []
#     for j in range(1,n+1,i):
#         c_ar.append(j)
#     if len(c_ar) >= 3:
#         ar.append(c_ar)
# print(ar)
# print(len(ar))
# for i in range(len(ar)):
#     print(ar[i])
#     print(len(ar[i]))
#     for j in range(len(ar[i])-2):
#         print(s[ar[i][j]-1],s[ar[i][j+1]-1],s[ar[i][j+2]-1])
#         print(ar[i][j]-1, ar[i][j+1]-1, ar[i][j+2]-1)
#         if s[ar[i][j]-1] != s[ar[i][j+1]-1] and s[ar[i][j+1]-1] != s[ar[i][j+2]-1] and s[ar[i][j+2]-1] != s[ar[i][j]-1]:
#             cnt += 1
#             print("Y")
#     print(cnt)
# print(a[0][1],a[1][1],a[2][1])
# print(a[0][1]*a[1][1]*a[2][1]-cnt)
if n == 1 or n == 2 or n == 3:
    print(0)
    exit()
if len(a) != 3:
    print(0)
    exit()
for i in range(1,n//2+3):
    cnt = 0
    #print(i)
    for j in range(n):
        if cnt + 2*i > n-1:
            break
        x,y,z = s[cnt], s[cnt+i], s[cnt+2*i]
        #print(cnt, cnt+i, cnt+i+i)
        if x != y and y != z and z != x:
            ans += 1
        cnt += 1
print(a[0][1]*a[1][1]*a[2][1]-ans)
import sys
n = int(input())
x = list(map(int, input().split()))
s = sorted([[y-1, i+1] for i, y in enumerate(x)])
cur = 0
cnt = [0 for _ in range(n+1)]
fill_cur = 0
ans = []
residual = []
for i in range(n*n):
	if i == s[cur][0] and cnt[s[cur][1]] != s[cur][1]-1:
		print("No")
		sys.exit()
	elif i == s[cur][0]:
		ans.append(s[cur][1])
		cnt[s[cur][1]] += 1
		residual += [s[cur][1]] * (n - s[cur][1])
		cur += 1
		fill_cur = max(fill_cur, cur)
		if cur == n:
			break
	elif fill_cur < n:
		if cnt[s[fill_cur][1]] == s[fill_cur][1]-1:
			fill_cur += 1
		if fill_cur == n:
			ans.append(residual.pop())
			continue
		fill_cur = max(fill_cur, cur)
		ans.append(s[fill_cur][1])
		cnt[s[fill_cur][1]] += 1
	else:
		ans.append(residual.pop())
ans += residual
print("Yes")
print(*ans)

### FIXED CODE ###

import sys
n = int(input())
x = list(map(int, input().split()))
s = sorted([[y-1, i+1] for i, y in enumerate(x)])
cur = 0
cnt = [0 for _ in range(n+1)]
fill_cur = 0
ans = []
residual = []
for i in range(n*n):
	if i == s[cur][0] and cnt[s[cur][1]] != s[cur][1]-1:
		print("No")
		sys.exit()
	elif i == s[cur][0]:
		ans.append(s[cur][1])
		cnt[s[cur][1]] += 1
		residual += [s[cur][1]] * (n - s[cur][1])
		cur += 1
		fill_cur = max(fill_cur, cur)
		if cur == n:
			break
	elif fill_cur < n:
		while cnt[s[fill_cur][1]] == s[fill_cur][1]-1:
			fill_cur += 1
			if fill_cur == n:
				if not residual:
					print("No")
					sys.exit()
				ans.append(residual.pop())
				break
		else:
			fill_cur = max(fill_cur, cur)
			ans.append(s[fill_cur][1])
			cnt[s[fill_cur][1]] += 1
	elif not residual:
		print("No")
		sys.exit()
	else:
		ans.append(residual.pop())
ans += residual
print("Yes")
print(*ans)
h, w = map(int, input().split())

if h == 1 or w == 1:
    c == 1
elif h & 1:
    if w & 1:
        c = ((h + 1) // 2) * ((w + 1) // 2) + (h // 2) * (w // 2)
    else:
        c = (((h + 1) // 2) + (h // 2)) * (w // 2)
else:
    c = (h // 2) * w

print(c)


### FIXED CODE ###

h, w = map(int, input().split())

if h == 1 or w == 1:
    c = 1
elif h & 1:
    if w & 1:
        c = ((h + 1) // 2) * ((w + 1) // 2) + (h // 2) * (w // 2)
    else:
        c = (((h + 1) // 2) + (h // 2)) * (w // 2)
else:
    c = (h // 2) * w

print(c)