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

from collections import deque
import sys
H,W=map(int,input().split())
S =[]
kuro=0
for i in range(H):
    s = list(input())
    for j in s:
        if j=='#':
            kuro +=1
    S.append(s)

visit=[[False]*W for i in range(H)]
dist=[[]]
kei=deque()
kei.append((0,0,1))
X =[-1,0,1,0]
Y=[0,-1,0,1]
while kei:
    y,x,d=kei.popleft()
    visit[y][x]=True
    if y==H-1 and x==W-1:
        print(H*W-d-kuro)
        sys.exit()
    for i in range(4):
        nx = x +X[i]
        ny = y +Y[i]
        if (0<=nx< W) and (0<=ny<H) and S[ny][nx]=='.':
            if not visit[ny][nx]:
                kei.append((ny,nx,d+1))
print(-1)

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**8)

H, W = map(int, input().split()) 
S = [list(input()) for i in range(H)]

Kuro = 0
Shiro = 0
for j in range(H):
    for i in range(W):
        if S[j][i]=='.':
            Shiro += 1
Dis =[[-1]*W for i in range(H)]
X =[-1, 0, 1, 0]
Y =[0, -1, 0, 1]
q = deque()
q.append((0,0))
Dis[0][0] = 0
a=deque()
while (q != a):
    y,x = q.popleft()
    if (y==H-1) and (x==W-1):
        break
    for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if (0<= nx < W) and(0 <= ny < H) and (S[ny][nx]=='.') and (Dis[ny][nx] ==-1):
            q.append((ny,nx))
            Dis[ny][nx] = Dis[y][x] +1

if (Dis[H-1][W-1]==-1):
    print(-1)
else:
    print(Shiro-Dis[H-1][W-1]-1)
### BUGGY CODE ###

n,m=map(int,input().split())
s=list(str(input()))
f=0
mf=0
for i in range(n+1):
    if s[i]=='1':
        f+=1
        mf=max(mf,f)
    else:
        f=0
if mf>=m:
    print(-1)
    exit()
reans=[]
s.reverse()
nk=0
while nk<n+1:
    for i in range(min(n-nk,m),0,-1):
        if s[nk+i]=='0':
            nk=nk+i
            reans.append(i)
            break
reans.reverse()
print(*reans)
        


### FIXED CODE ###

n,m=map(int,input().split())
s=list(str(input()))
f=0
mf=0
for i in range(n+1):
    if s[i]=='1':
        f+=1
        mf=max(mf,f)
    else:
        f=0
if mf>=m:
    print(-1)
    exit()
reans=[]
s.reverse()
nk=0
while nk<n:
    for i in range(min(n-nk,m),0,-1):
        if s[nk+i]=='0':
            nk=nk+i
            reans.append(i)
            break
reans.reverse()
print(*reans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a_uni = list(set(a))

a_ol = {}
def_count = 0
for i in a_uni:
    a_co = a.count(i)
    a_ol[i] = a_co
    def_count += a_co * (a_co - 1)

def_count //= 2

for k in a:
    print(def_count - a_ol[k] + 1)



### FIXED CODE ###

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


a_ol = Counter(a)
def_count = 0
for item in a_ol.items():
    a_co = item[1]
    def_count += a_co * (a_co - 1)

def_count //= 2

for k in a:
    print(def_count - a_ol[k] + 1)
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]
table = [[int(i) for i in input().split()] for m in range(m)]

a = range(table[0][0],table[0][1]+1)
ans = a
for i,t in enumerate(table[1:]):
    if i == 0:
    	b = range(t[0], t[1]+1)
    	ans = set(a) & set(b)
    else:
        b = range(t[0], t[1]+1)
        ans = ans & set(b)
print(len(ans))

### FIXED CODE ###

n,m=map(int,input().split())
low=1
high=n
for i in range(m):
	l,r=map(int,input().split())
	low = max(low,l)
	high=min(high,r)
ans=high-low+1
print(ans if ans>=0 else 0)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
    ans*=i
if ans>1000000000000000000:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
su=0
count=0
for j in a:
    if j==0:
        su+=1
        break
if su>0:
    print(0)
else:
    for i in a:
        ans*=i
        if ans>1000000000000000000:
            print(-1)
            count+=1
            break
    if count!=1:
        if ans>1000000000000000000:
            print(-1)
        else:
            print(ans)
### BUGGY CODE ###

def solve():
    import numpy as np
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    A = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    B = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    
    max_bias = 80 * (W - 1) * (H - 1)
    dp1 = np.full((W, max_bias), False)
    dp1[0][0] = True
    for A_i, B_i in zip(A, B):
        dp2 = np.full((W, max_bias), False)
        diff = A_i[0] - B_i[0]
        for pre_bias in np.where(dp1[0] == True)[0]:
            dp2[0][abs(pre_bias + diff)] = True
            dp2[0][abs(pre_bias - diff)] = True
            
        for j, t in enumerate(zip(A_i[1:], B_i[1:]), start=1):
            A_ij, B_ij = t
            diff = A_ij - B_ij
            for pre_bias in np.where(dp1[j] == True)[0]:
                dp2[j][abs(pre_bias + diff)] = True
                dp2[j][abs(pre_bias - diff)] = True
            for pre_bias in np.where(dp2[j-1] == True)[0]:
                dp2[j][abs(pre_bias + diff)] = True
                dp2[j][abs(pre_bias - diff)] = True
        dp1 = dp2
    
    print(np.where(dp2[-1] == True)[0][0])
 
solve()

### FIXED CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    A = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    B = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    
    dp1 = [0] * W
    bit_width = 80 * (H + W - 2)
    dp1[0] = 1 << (bit_width)
    for A_i, B_i in zip(A, B):
        dp2 = [0] * W
        
        diff = abs(A_i[0] - B_i[0])
        dp2[0] = (dp1[0] << diff) | (dp1[0] >> diff)
        
        for j, t in enumerate(zip(A_i[1:], B_i[1:]), start=1):
            A_ij, B_ij = t
            diff = abs(A_ij - B_ij)
            b = dp1[j] | dp2[j-1]
            dp2[j] = (b << diff) | (b >> diff)
        
        dp1 = dp2
    
    b = bin(dp2[-1])
    b = b[-bit_width-1:]
    print(b.index('1'))
 
solve()
### BUGGY CODE ###

n,ma,mb=map(int,input().split())
dp=[[[9999]*401for _ in range(401)]for _ in range(n+1)];dp[0][0][0]=0
sa=sb=0
for i in range(1,n+1):
  a,b,c=map(int,input().split())
  sa+=a;sb+=b
  for j in range(401):
    for k in range(401):
      if j>=a and k>=b:dp[i][j][k]=min(dp[i-1][j-a][k-b]+c,dp[i-1][j][k])
      else:dp[i][j][k]=dp[i-1][j][k]
a=9999
for i in range(1,min(sa//ma,sb//mb)+1):
  if dp[n][ma*i][mb*i]!=9999:a=min(a,dp[n][ma*i][mb*i])
print(-1if a==9999else a)

### FIXED CODE ###

n,ma,mb=map(int,input().split())
dp=[[[5000]*401for _ in range(401)] for _ in range(n+1)]
dp[0][0][0]=0
maa=mab=0
for i in range(1,n+1):
  a,b,c=map(int,input().split())
  maa+=a
  mab+=b
  for j in range(401):
    for k in range(401):dp[i][j][k]=min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
ans=5000
for i in range(1,min(maa//ma,mab//mb)+1):
  if dp[n][ma*i][mb*i]!=5000:ans=min(ans,dp[n][ma*i][mb*i])
print(-1if ans==5000else ans)
### BUGGY CODE ###

import sys

h,w=list(map(int,input().split()))
s=[]

left=[[0]*w for _ in range(h)]
right=[[0]*w for _ in range(h)]
up=[[0]*w for _ in range(h)]
down=[[0]*w for _ in range(h)]

for i in range(h):
    s.append([x for x in sys.stdin.readline().strip()])

for i in range(h):
    cntl=0
    cntr=0
    for jl in range(w):
        jr=w-jl-1

        if s[i][jl]=='#':
            cntl=0
        else:
            cntl+=1
        
        if s[i][jr]=='#':
            cntr=0
        else:
            cntr+=1
        
        left[i][jl]=cntl
        right[i][jr]=cntr

for j in range(w):
    cntu=0
    cntd=0
    for iu in range(h):
        id=h-iu-1

        if s[iu][j]=='#':
            cntu=0
        else:
            cntu+=1
        
        if s[id][j]=='#':
            cntd=0
        else:
            cntd+=1
        
        up[iu][j]=cntu
        down[id][j]=cntd
ret=0

for i in range(h):
    for j in range(w):
        ret=max(ret,left[i][j]+right[i][j]+up[i][j]+down[i][j]-3)

print(ret)


### FIXED CODE ###

import sys

h,w=list(map(int,input().split()))
s=[]

left=[[0]*w for _ in range(h)]
right=[[0]*w for _ in range(h)]
up=[[0]*w for _ in range(h)]
down=[[0]*w for _ in range(h)]

for i in range(h):
    s.append([x for x in sys.stdin.readline().strip()])

for i in range(h):
    cntl=0
    cntr=0
    for jl in range(w):
        jr=w-jl-1

        if s[i][jl]=='#':
            cntl=0
        else:
            cntl+=1
        
        if s[i][jr]=='#':
            cntr=0
        else:
            cntr+=1
        
        left[i][jl]=cntl
        right[i][jr]=cntr

for j in range(w):
    cntu=0
    cntd=0
    for iu in range(h):
        id=h-iu-1

        if s[iu][j]=='#':
            cntu=0
        else:
            cntu+=1
        
        if s[id][j]=='#':
            cntd=0
        else:
            cntd+=1
        
        up[iu][j]=cntu
        down[id][j]=cntd
ret=0

for i in range(h):
    for j in range(w):
        ret=max(ret,left[i][j]+right[i][j]+up[i][j]+down[i][j]-3)

print(ret)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
A.reverse()
Ans = []
d = 0
cnt = 0
while cnt < 2:
  c = A.count(A[d])
  for j in range(c//2):
    Ans.append(A[d])
  cnt += c//2
  d += c
  if d == N:
    Ans.append(0)
    Ans.append(0)
    cnt +=2
print(Ans[0]*Ans[1])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
Ans = []
d = 0
cnt = 0
while cnt < 2:
  c = (A[d:d+4]).count(A[d])
  for j in range(c//2):
    Ans.append(A[d])
  cnt += c//2
  d += c
  if d == N:
    Ans.append(0)
    Ans.append(0)
    cnt +=2
print(Ans[0]*Ans[1])
### BUGGY CODE ###

import sys

n = int(input())
ds = [list(map(int, input().split())) for _ in range(n)]
mod = (ds[0][0] + ds[0][1]) % 2
for i in range(2, n):
	if (ds[i][0] + ds[i][1]) % 2 != mod:
		print(-1)
		sys.exit()

m = max([abs(ds[i][0]) + abs(ds[i][1]) for i in range(n)])
if m == 0:
	print(2)
	print(1, 1)
	for _ in range(n):
		print("LR")
else:
	print(m)
	print(*[1 for _ in range(m)])
	for d in ds:
		ans = []
		if d[0] >= 0:
			ans += ["R"] * d[0]
		else:
			ans += ["L"] * abs(d[0])
		if d[1] >= 0:
			ans += ["U"] * d[1]
		else:
			ans += ["D"] * abs(d[1])
		ans += ["LR"] * ((m - abs(d[0]) - abs(d[1])) // 2)
		print(*ans, sep="")

### FIXED CODE ###

import sys

n = int(input())
ds = [list(map(int, input().split())) for _ in range(n)]
mod = (ds[0][0] + ds[0][1]) % 2
for i in range(2, n):
	if (ds[i][0] + ds[i][1]) % 2 != mod:
		print(-1)
		sys.exit()

if mod == 1:
	m = 31
	arms = [1<<i for i in range(31, 0, -1)]
else:
	m = 32
	arms = [1<<i for i in range(31, 0, -1)] + [2]

print(m)
print(*[a//2 for a in arms])

for q in range(n):
	x, y = ds[q][0], ds[q][1]
	ans = ""
	u, v = x+y + (1<<31) - 1, x-y + (1<<31) - 1
	if mod == 0:
		u, v = u-1, v-1
	u_li = []
	v_li = []
	for i in range(31, 0, -1):
		if u >= (1<<i):
			u_li.append(1)
			u -= (1<<i)
		else:
			u_li.append(0)
		if v >= (1<<i):
			v_li.append(1)
			v -= (1<<i)
		else:
			v_li.append(0)

	for i in range(31):
		if u_li[i] and v_li[i]:
			ans += "R"
		elif u_li[i]:
			ans += "U"
		elif v_li[i]:
			ans += "D"
		else:
			ans += "L"

	if mod == 0:
		ans += "R"

	print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    import numpy as np

    N, K = map(int, input().split())
    S = set()
    section = []
    for _ in range(K):
        l, r = map(int, input().split())
        section.append((l, r + 1))
        for n in range(l, r + 1):
            S.add(n)
    MOD = 998244353

    dp = np.zeros(N, dtype=np.int64)
    dp[0] = 1
    for i in range(N):
        # for d in S:
        #     if i >= d:
        #         dp[i] += dp[i - d] % MOD
        for left, right in section:
            right = min(i + right, N)
            left = i + left
            dp[left:right] += dp[i]
    print(dp[-1] % MOD)
    # print(dp)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    import numpy as np

    N, K = map(int, input().split())
    section = [list(map(int, input().split())) for _ in range(K)]
    MOD = 998244353

    dp = np.zeros(N + 1, dtype=np.int64)
    dp[1] = 1
    cumsum = np.zeros(N + 1, dtype=np.int64)
    cumsum[1] = 1
    for i in range(2, N + 1):
        for left_section, right_section in section:
            left = max(i - right_section - 1, 0)
            right = i - left_section
            if right < 0:
                continue
            dp[i] += cumsum[right] - cumsum[left]
        cumsum[i] = cumsum[i - 1] + dp[i]
        dp[i] %= MOD
        cumsum[i] %= MOD
    print(dp[N] % MOD)
    # print(dp)
    # print(cumsum)


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

#import numpy as np

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

#dp[S] = A[S], -inf で初期化　Sの部分集合TのうちA[T]が(最大のもの, 次に大きいもの)　を入れていく

dp = [[A[S], -float('inf') ] for S in range(1 << N)]
for i in range(N):
    for T in range( 1 << N):
        if (T >> i) & 1 == 1: # Tがiを含むとき
            merge = dp[T] + dp[T ^ (1 << i)]
            merge.sort(reverse = True)
            dp[T] =merge[:2]
ans = -float('inf')
for S in range(1, 1 << N , 1):
    ans = max(ans, sum(dp[S]))
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
#dp[S] = A[S], -inf で初期化　Sの部分集合TのうちA[T]が(最大のもの, 次に大きいもの)　を入れていく
 
dp = [[A[S], -float('inf') ] for S in range(1 << N)]
for i in range(N):
    for T in range( 1 << N):
        if (T >> i) & 1 == 1: # Tがiを含むとき
            merge = dp[T] + dp[T ^ (1 << i)]
            merge.sort(reverse = True)
            dp[T] =merge[:2]
ans = -float('inf')
for S in range(1, 1 << N , 1):
    ans = max(ans, sum(dp[S]))
    print(ans)
### BUGGY CODE ###

S = input()

ans = 0
for i in range(len(S)):
    m = int(S[i])
    for j in range(i + 1, len(S)):
        m = (10 * m + int(S[j])) % 2019
        if m == 0:
            ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter

S = input()

ans = 0
mod_list = [0] * len(S)
mod_list[-1] = int(S[-1])
m = 1
for i in range(2, len(S) + 1):
    m = (10 * m) % 2019
    mod_list[-i] = (mod_list[-i + 1] + (int(S[-i]) * m)) % 2019

mod_counter = Counter(mod_list)
mod_counter[0] += 1

ans = 0
for _, v in mod_counter.items():
    ans += v * (v - 1) // 2

print(ans)
### BUGGY CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-

DIR = [
	(1, 0),
	(0, -1),
	(-1, 0),
	(0, 1),
]

def main():
	s = raw_input()
	s2 = raw_input()
	x, y = [int(x) for x in s2.split()]
	# print s, x, y

	dp = set([(0,0,0)])
	for instr in s:
		if instr == 'F':
			dp = set([(t[0]+DIR[t[2]][0], t[1]+DIR[t[2]][1], t[2]) for t in dp])
		else:
			dp = set([(t[0], t[1], (t[2]+1)%4) for t in dp]) | set([(t[0], t[1], (t[2]-1+4)%4) for t in dp])

	for i in xrange(4):
		if (x, y, i) in dp:
			print 'Yes'
			return
	print 'No'

if __name__ == '__main__':
	main()

### FIXED CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-

def main():
	s = raw_input()
	s2 = raw_input()
	x, y = [int(x) for x in s2.split()]
	# print s, x, y

	xt, yt = [], []
	d, step = 0, 0
	for c in s:
		if c == 'T':
			if d == 0:
				xt.append(step)
			else:
				yt.append(step)
			step = 0
			d = 1 - d
		else:
			step += 1
	if step > 0:
		if d == 0:
			xt.append(step)
		else:
			yt.append(step)

	x -= xt[0]
	xt = xt[1:]
	xd, yd = set([0]), set([0])
	for t in xt:
		xd2 = set()
		for i in xd:
			xd2.add(i + t)
			xd2.add(i - t)
		xd = xd2
	for t in yt:
		yd2 = set()
		for i in yd:
			yd2.add(i + t)
			yd2.add(i - t)
		yd = yd2

	if x in xd and y in yd:
		print 'Yes'
	else:
		print 'No'


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

N=int(input())
x=1
for a in list(map(int,input().split())):
    x*=a
print(-1 if x>10**18 else x)

### FIXED CODE ###

_=input()
A=sorted(list(map(int,input().split())))
B=1
for a in A:
    B*=a
    if B>10**18:
        B=-1
        break
print(B)
### BUGGY CODE ###

H,N = map(int, input().split())
dp = [0]+[float("inf")]*H
for n in range(N):
  A,B = map(int, input().split())
  for h in range(1,H+1):
    dp[h] = min(dp[h],dp[max(0,h-A)]+B)
print(dp[-1])

### FIXED CODE ###

H,N,*AB = map(int, open(0).read().split())
dp = [0]+[10**8]*H
for n in range(N):
  A,B = AB[2*n:2*(n+1)]
  for h in range(1,H+1): dp[h] = min(dp[h],dp[max(0,h-A)]+B)
print(dp[-1])
### BUGGY CODE ###

n = int(input())
aa = list(map(int,input().split()))

a = []
for i in range(n):
    a.append(aa[i]-(i+1))
    
b = {}
for i in a:
    if i in b:
        b[i] += 1
    else:
        b.update({i:1})
        
ans_l = []
for k in b.keys():
    counts = 0
    for k_, val in b.items():
        counts += (abs(k - k_)) * val
    ans_l.append(counts)
    
print(min(ans_l))

### FIXED CODE ###

n = int(input())
aa = list(map(int,input().split()))

a = []
for i in range(n):
    a.append(aa[i]-(i+1))
b = list(sorted(a))

ans = 0

for i in range(n//2):
    ans += b[-i-1] - b[i]
print(ans)
### BUGGY CODE ###

import copy
N = int(input())
T = list(map(int,input().split()))
T.sort()
ANSL = []
for i in range(len(T)):
    S = copy.copy(T)
    S.pop(i)
    ANS = 0
    while True:
        S.sort()
        LIS = []
        if S[0] == 1:
            ANS += 1
            break
        elif len(S) == 1:
            ANS += S[0]
            break
        else:
            LIS.append(S[0])
            for k in range(len(S)-1):
                if (S[k+1] % S[k] == 0) or (S[k+1] % LIS[0] == 0):
                    continue
                else:
                    LIS.append(S[k+1] % S[k])
                    LIS.sort()
        S = LIS
    ANSL.append(ANS)
print(max(ANSL))


### FIXED CODE ###

import copy 

def gcd(a,b):
    if b > a:
        a, b = b, a
    while b:
        a, b = b, a%b
    return a

N = int(input())
T = list(map(int,input().split()))
T.sort()
LIS = [0]*N
LIS[0] += T[0]
for i in range(N-1):
    LIS[i+1] += gcd(LIS[i],T[i+1])
F = LIS.index(min(LIS))
if len(T) == 2:
    ANS = max(T[0],T[1])
elif F == 0:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(1)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANS = max(ANSU,ANSV)
    
else:
    U = copy.copy(T)
    V = copy.copy(T)
    U.pop(F)
    V.pop(0)
    LU = [0]*(N-1)
    LU[0] = U[0]
    LV = [0]*(N-1)
    LV[0] = V[0]
    ANSU = 0
    ANSV = 0
    for i in range(N-2):
        LU[i+1] += gcd(LU[i],U[i+1])
    ANSU = LU[N-2]
    for i in range(N-2):
        LV[i+1] += gcd(LV[i],V[i+1])
    ANSV = LV[N-2]
    ANSP = max(ANSU,ANSV)
    ANS = max(ANSP,LIS[N-1])
        
print(ANS)
### BUGGY CODE ###

from math import gcd
from functools import reduce
from sys import exit

# O(A+NloglogN)解
MAX_A = 1000000
lowerst_prime = [10**9] * (MAX_A + 1) # 最小の素因数をいれる(2以上をみていけばいい)
count = [0] * (MAX_A + 1) # 約数として出てくる回数を数える

for i in range(2, MAX_A + 1): # エラトステネスの篩
    if lowerst_prime[i] != 10**9:
        continue
    lowerst_prime[i] = i
    for j in range(i * i, MAX_A + 1, i): # i * iスタートでいいのは、i * bはbの約数でもあるため
        if lowerst_prime[j] == 10**9:
            lowerst_prime[j] = i
# 入力
N = int(input())
A = [*map(int, input().split())]

if reduce(gcd, A) != 1:
    print("not coprime")
    exit(0)

for i in range(N):
    while A[i] > 1:
        divide = lowerst_prime[A[i]]
        count[divide] += 1
        while A[i] % divide == 0: # 割れるだけ割る
            A[i] //= divide

for i in range(MAX_A + 1):
    if count[i] >= 2:
        print("setwise coprime")
        exit(0)
print("pairwise coprime")

### FIXED CODE ###

from math import gcd
from functools import reduce
from sys import exit

# O(NlogA+AloglogA)解
MAX_A = 1000000
lowerst_prime = [10**9] * (MAX_A + 1) # 最小の素因数をいれる(2以上をみていけばいい)
count = [0] * (MAX_A + 1) # 約数として出てくる回数を数える

for i in range(2, MAX_A + 1): # エラトステネスの篩
    if lowerst_prime[i] != 10**9:
        continue
    lowerst_prime[i] = i
    for j in range(i * i, MAX_A + 1, i): # i * iスタートでいいのは、i * bはbの約数でもあるため
        if lowerst_prime[j] == 10**9:
            lowerst_prime[j] = i
# 入力
N = int(input())
A = [*map(int, input().split())]

if reduce(gcd, A) != 1:
    print("not coprime")
    exit(0)

for i in range(N):
    while A[i] > 1:
        divide = lowerst_prime[A[i]]
        count[divide] += 1
        while A[i] % divide == 0: # 割れるだけ割る
            A[i] //= divide

for i in range(MAX_A + 1):
    if count[i] >= 2:
        print("setwise coprime")
        exit(0)
print("pairwise coprime")
### BUGGY CODE ###

import numpy as np
n = int(input())
dif = np.array(list(map(int, input().split())))
divide = 0
for k in range(min(dif), max(dif)+1):
    count_over = 0
    count_under = 0
    for i in range(len(dif)):
        if dif[i] >= k:
            count_over += 1
        else:
            count_under += 1
    if count_over == count_under:
        divide += 1
print(divide)

### FIXED CODE ###

n = int(input())
dif = list(map(int, input().split()))
dif.sort()

divide = 0

medium = int((len(dif)) / 2)


if (len(dif)) %2 != 0:
    print(divide)
else:
    divide = dif[medium] - dif[medium-1]
    print(divide)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[]
for i in range(n):
    ans+=[a.index(i+1)+1]
print(*ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(range(1,n+1))
dic=dict(zip(a,b))
dic=sorted(dic.items())
c=[]
for i in dic:
    c.append(i[1])
print(*c)
### BUGGY CODE ###

from collections import deque

N, *AB = map(int, open(0).read().split())

E = [set() for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add((b, i))
    E[b].add((a, i))

K = max(len(e) for e in E)
A = [0] * (N - 1)
Q = deque([(-1, 1)])
S = {c for c in range(1, K + 1)}
while Q:
    p, v = Q.popleft()
    C = S - {p}
    for u, i in E[v]:
        E[u].remove((v, i))
        c = C.pop()
        Q.append((c, u))
        A[i] = c

print(K)
for a in A:
    print(a)


### FIXED CODE ###

from collections import deque

def main():
    N, *AB = map(int, open(0).read().split())

    E = [set() for _ in range(N + 1)]

    memo = {}
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        E[a].add(b)
        E[b].add(a)
        memo[(a, b)] = i
        memo[(b, a)] = i

    K = max(len(e) for e in E)

    A = [""] * (N - 1)

    visited = [False] * (N + 1)

    Q = deque([(-1, 1)])
    visited[1] = True
    while Q:
        a, v = Q.popleft()
        c = 0
        for u in E[v]:
            E[u].remove(v)
            c += 1
            if c == a:
                c += 1
            Q.append((c, u))
            A[memo[(v, u)]] = str(c)
        E[v] = set()
    print(K)
    print("\n".join(A))

main()
### BUGGY CODE ###

import collections
import itertools
def main():
    N = int(input())
    A = list(map(lambda x:x-1 ,map(int, input().split())))

    coll = collections.Counter(A[1:])
    counter = [0]*N
    comb = [0]*N
    for i in range(N):
        c=coll.get(i,0)
        counter[i] = c
        if c>1:
            comb[i] = len(list(itertools.combinations([i for i in range(c)],2)))
    sum1 = sum(comb)
    print(sum1)

    for i in range(1,N):
        # ボールA[i-1]を復活させて、ボールA[i]を除外
        n = counter[A[i-1]]
        if n>=1:
            sum1 += n
        counter[A[i-1]] += 1
        n = counter[A[i]]
        if n>=2:
            sum1 -= n-1
        counter[A[i]] -= 1
        print(sum1)

main()


### FIXED CODE ###

from operator import mul
from functools import reduce
import collections

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def main():
    N = int(input())
    A = list(map(lambda x:x-1 ,map(int, input().split())))

    coll = collections.Counter(A[1:])
    counter = [0]*N
    comb = [0]*N
    sum1 = 0
    for i in range(N):
        c=coll.get(i,0)
        counter[i] = c
        if c>1:
            comb[i] = combinations_count(c,2)
            sum1 += comb[i]
    print(sum1)

    for i in range(1,N):
        # ボールA[i-1]を復活させて、ボールA[i]を除外
        n = counter[A[i-1]]
        if n>=1:
            sum1 += n
        counter[A[i-1]] += 1
        n = counter[A[i]]
        if n>=2:
            sum1 -= n-1
        counter[A[i]] -= 1
        print(sum1)

main()