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

import re

H, W = map(int, input().split())
S_list = [input() for _ in range(H)]

l_wall = [[i.span()[0] for i in re.finditer('#', '#'+s+'#')] for s in S_list]
r_wall = [[i.span()[0] for i in re.finditer('#', '#'+''.join(s)+'#')] for s in list(zip(*S_list))]

l_light = sum([[i[j+1]-i[j]-1 for j in range(len(i)-1)] if len(i) != 1 else i for i in l_wall], [])
r_light = sum([[i[j+1]-i[j]-1 for j in range(len(i)-1)] if len(i) != 1 else i for i in r_wall], [])

ans = max([l+r-1 for l in l_light for r in r_light])

print(ans)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S_list = [list(input()) for _ in range(H)]
S_list=(np.array(S_list) ==".")*1

L = np.zeros((H, W), int)
R = np.zeros((H, W), int)
U = np.zeros((H, W), int)
D = np.zeros((H, W), int)

for w in range(W):
    if w == 0:
        L[:,w] = S_list[:,w]
        R[:,W-w-1] = S_list[:,W-w-1]
    else:
        L[:,w] = (L[:,w-1]+1) * S_list[:,w]
        R[:,W-w-1] = (R[:,W-w]+1) * S_list[:,W-w-1]

for h in range(H):
    if h == 0:
        U[h,:] = S_list[h,:]
        D[H-h-1,:] = S_list[H-h-1,:]
    else:
        U[h,:] = (U[h-1,:]+1) * S_list[h,:]
        D[H-h-1,:] = (D[H-h,:]+1) * S_list[H-h-1,:]
        
ans = max(np.max(L+R+U+D-3), 0)

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

import sys
#input = sys.stdin.buffer.readline
from collections import defaultdict

def main():
    S = input()
    
    l = []
    base = 1
    for st in S[::-1]:
        l.append((int(st)*base)%2019)
        base *= 10
        
    cum = 0
    d = defaultdict(int)
    d[0] = 1
    
    for num in l:
        cum += num
        d[cum%2019] += 1

    ans = 0
    for num in d.values():
        ans += (num*(num-1))//2
    
    print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline
from collections import Counter

def main():
    S = input()
    P = 2019

    ans,base = 0,1
    MOD_list = [0]

    for st in S[::-1]:
        num = int(st)
        MOD = (MOD_list[-1]+num*base)%P
        MOD_list.append(MOD)
        base *= 10
        base %= P

    c = Counter(MOD_list)
    for v in c.values():
        ans += (v*(v-1))//2
        
    print(ans)

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

X , K ,D = map(int, input().split())


if X>0:
    for k in range(K):
        bx = X
        X-=D
        if X<=0:
            break
else:
    for k in range(K):
        bx = X
        X+=D
        if X>=0:
            break

if K == k + 1 or (K-k-1)%2==0:
    print(abs(X))
else:
    print(abs(bx))

### FIXED CODE ###

X , K ,D = map(int, input().split())


if X>0:
    S = int(abs(X) / D)
    aX = X -D * S
    if S>=K:
        print(X-D*K)
    elif (K-S)%2==0:
        print(abs(aX))
    else:
        print(abs(aX-D))
else:
    S = int(abs(X) / D)
    aX = X + D * S
    if S>=K:
        print(abs(X+D*K))
    elif (K-S)%2==0:
        print(abs(aX))
    else:
        print(abs(aX+D))
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
new_l = []
q = 0
for i in l:
  new_l.append(i)
  a = sorted(new_l)
  if a.index(i)==0:
    q += 1
print(q)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
q = 1
a = l[0]
for i in range(1,n):
  a = min(l[i],a)
  if l[i]<=a:
    q += 1
print(q)
### BUGGY CODE ###

n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
result = sum(a)
b_ = []
for i in range(m):
    b, c = map(int, input().split(' '))
    tmp = [c] * b
    b_ += tmp
b_.sort(reverse=True)
a.sort()
if len(b_) > n:
    b_ = b_[:n]
for j,k in zip(a, b_):
    if j < k:
        a[a.index(j)] = k
    else:
        break
print(sum(a))


### FIXED CODE ###


n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
result = sum(a)
b_ = []
for i in range(m):
    b, c = map(int, input().split(' '))
    b_ += [(b,c)]
for i in range(n):
    b_ += [(1, a[i])]

from operator import itemgetter
b_.sort(key=itemgetter(1), reverse=True)

count = n
res = 0
for j, k in b_:
    if count > j:
        res += k * j
        count -= j
    elif count <= j:
        res += k * count
        break
print(res)
### BUGGY CODE ###

inf = float('inf')

#計算量O(V^3) V:頂点数
# dist[i][j]: iからjへのコスト,  n:頂点数
def warshall_floyd(ad):
    n = len(ad)
    dist = [line[:] for line in ad]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    dist[i][j] = 0
                elif dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int,input().split())
ad = [[inf] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int,input().split())
    if C > L:
        continue
    A -= 1
    B -= 1
    ad[A][B] = C
    ad[B][A] = C
Q = int(input())
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]

ad = warshall_floyd(ad)
for s in range(N):
    for t in range(N):
        if ad[s][t] <= L:
            ad[s][t] = 1
        else:
            ad[s][t] = inf

ad = warshall_floyd(ad)
for s, t in query:
    ans = ad[s][t] - 1
    if ans == inf:
        ans = -1
    print(ans)

### FIXED CODE ###

inf = float('inf')

#計算量O(V^3) V:頂点数
# dist[i][j]: iからjへのコスト,  n:頂点数
def warshall_floyd(ad):
    n = len(ad)
    dist = [line[:] for line in ad]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    dist[i][j] = 0
                elif dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

N, M, L = map(int,input().split())
ad = [[inf] * N for _ in range(N)]
for _ in range(M):
    A, B, C = map(int,input().split())
    if C > L:
        continue
    A -= 1
    B -= 1
    ad[A][B] = C
    ad[B][A] = C
Q = int(input())
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]

ad = warshall_floyd(ad)
for s in range(N):
    for t in range(N):
        if ad[s][t] <= L:
            ad[s][t] = 1
        else:
            ad[s][t] = inf

ad = warshall_floyd(ad)
for s, t in query:
    ans = ad[s][t] - 1
    if ans == inf:
        ans = -1
    print(ans)
### BUGGY CODE ###

import sys
cnt = 1
while 1:
    x = sys.stdin.readline().strip()
    if x == 0:
        break
    print("Case {}: {}".format(cnt,x))
    cnt += 1

### FIXED CODE ###

import sys
cnt = 1
while True:
    x = sys.stdin.readline().strip()
    if x == "0":
        break
    print("Case {}: {}".format(cnt,x))
    cnt += 1
### BUGGY CODE ###

import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
num = 2 ** (max(int(math.log2(max(a))) + 1, int(math.log2(k + 0.0001)) + 1))
for i in range(n):
    a[i] = bin(a[i] + num)[3:]
binary = [[i,0,0] for i in range(int(math.log2(num)))]
for i in range(n):
    for j in range(int(math.log2(num))):
        if a[i][j] == "0":
            binary[int(math.log2(num)) - j - 1][1] += 1
        else:
            binary[int(math.log2(num)) - j - 1][2] += 1
binary.sort(reverse = True)
ans = 0
check = 0
for i in range(len(binary)):
    if binary[i][1] > binary[i][2]:
        check += 2 ** binary[i][0]
        if check <= k:
            ans += binary[i][1] * (2 ** binary[i][0])
        else:
            check -= 2 ** binary[i][0]
            ans += binary[i][2] * (2 ** binary[i][0])
    else:
        ans += binary[i][2] * (2 ** binary[i][0])
print(ans)

### FIXED CODE ###

import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
num = 2 ** (max(int(math.log2(max(a))) + 1, int(math.log2(k + 0.0001)) + 1))
num2 = int(math.log2(num))
for i in range(n):
    a[i] = bin(a[i] + num)[3:]
binary = [[i,0,0] for i in range(num2)]
for i in range(n):
    for j in range(num2):
        if a[i][j] == "0":
            binary[num2 - j - 1][1] += 1
        else:
            binary[num2 - j - 1][2] += 1
binary.sort(reverse = True)
ans = 0
check = 0
for i in range(len(binary)):
    if binary[i][1] > binary[i][2]:
        check += 2 ** binary[i][0]
        if check <= k:
            ans += binary[i][1] * (2 ** binary[i][0])
        else:
            check -= 2 ** binary[i][0]
            ans += binary[i][2] * (2 ** binary[i][0])
    else:
        ans += binary[i][2] * (2 ** binary[i][0])
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())

ans_list = {}

for i in range(N):
    for j in range(i+1, N):
        if not S[j + 1:N]:
            continue
        elif S[i] + S[j] not in ans_list:
            ans_list[S[i] + S[j]] = S[j + 1:N]
count = 0
# print(ans_list)
ans_len_list = [len(set(value)) for value in ans_list.values()]
print(sum(ans_len_list))

### FIXED CODE ###

N = int(input())
S = list(input())
visited = {}

count = 0

for i, s in enumerate(S):
    if s in visited:
        continue
    visited[s] = []
    for j, s2 in enumerate(S[i+1:N-1]):
        # print(s, s2, S[i + j + 2:N])
        if s2 in visited[s]:
            continue
        count += len(set(S[i + j + 2:N]))
        visited[s].append(s2)
        # print(s, s2, set(S[j + 1:N]))
print(count)
### BUGGY CODE ###

k,s = map(int,input().split())

counter = 0

for x in range(k+1):
    if s-x > 2 * k:
        continue
    for y in range(k+1):
        if s-x-y > k:
            continue
        if s-x-y <= k and s-x-y >=0:
            counter += 1
                
print(counter)

### FIXED CODE ###

k,s = map(int,input().split())
counter = 0

for x in range(k+1):
    if s-x > 2*k:
        continue
    for y in range(k+1):
        if s-x-y > k or s-x-y < 0:
            continue
        else:
            counter += 1
            
print(counter)
### BUGGY CODE ###

from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return

def gau(n):
    return n*(n+1)/2

def main():
    N = int(input())
    mods = [ i+1for i in range(N)]
    test = [mods[-1]]+mods[:-1]
    print(int(gau(N-1)))

if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return

def gau(n):
    return n*(n+1)//2

def main():
    N = int(input())
    if (N==1):
        print(0)
    else:
        print(gau(N-1))

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

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, LR):
    mod = 998244353
    S = []
    for lr in LR:
        S += [i for i in range(lr[0], lr[1] + 1)]
    S.sort()
    dp = [0] * (N + 1)
    dp[1] = 1
    for i in range(1, N + 1):
        for s in S:
            if i + s > N:
                break
            dp[i + s] = (dp[i + s] + dp[i]) % mod
    print(dp[N])


if __name__ == '__main__':
    N, K = map(int, input().split())
    LR = [[int(i) for i in input().split()] for _ in range(K)]
    solve(N,K,LR)

    # # test
    # from random import randint
    # from func import random_str
    # N, K = 2 * 10 ** 5, 1
    # LR = [[1, N]]
    # solve(N, K, LR)


### FIXED CODE ###

# 解説などを参考に作成
"""
N = 10, LR = [2, 4] を例とする.
fi:=マスiまで移動する方法の個数とおく.
便宜上0マスから始めると、
    N:  0 1 2 3 4 5 6 7 8 9 10
    fi: 0 1 0 1 1 2 2 4 5 8 11
となる.(1マス目には最初からいるのでf1 = 1とする.)
ここで、N=5,6の時で考えると、LR=[2,4]から
    f5 = f1 + f2 + f3  (∵2～4マス前からしか遷移がないので)
    f6 =      f2 + f3 + f4
よってf5とf6の差はf1とf4によって求めることができる.
    f6 = f5 - f1 + f4
一般化すると、
    fi = fi-1 - fi-1-R + fi-L
LRが複数ある場合でも区間が重複しないので、各区間に対して - fi-1-R + fi-L 部分を計算して fi を求めることができる.
計算量はO(KN) (K:=重複しない区間LRの個数)
"""


# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, LR):
    mod = 998244353
    dp = [0] * (N + 1)
    dp[1] = 1
    # dp[0] は基本0として扱ってよいが, dp[2]の計算時のみ,dp[0]とdp[1]の差分=0となる必要がある.
    # => この時のみ、dp[0]を1として計算しないと fi = fi-1 - fi-1-R + fi-L のルールに合わなくなる.
    # 他の人の解答(#16897281, #16895566)見ると階差数列？敵なのを持つことで解決できそうだったけど,
    # 内容が理解できなかったのでdp[2]までは手動実装することにした.
    dp[2] = 1 if 1 in [lr[0] for lr in LR] else 0
    for i in range(3, N + 1):
        x = 0
        for l, r in LR:
            x += dp[max(i - l, 0)] - dp[max(i - 1 - r, 0)]
        dp[i] = (dp[i - 1] + x) % mod
    print(dp[N])


if __name__ == '__main__':
    N, K = map(int, input().split())
    LR = [[int(i) for i in input().split()] for _ in range(K)]
    solve(N, K, LR)

    # # test
    # from random import randint
    # from func import random_str
    # N, K = 2 * 10 ** 5, 1
    # LR = [[1, N]]
    # solve(N, K, LR)
### BUGGY CODE ###

def main():
  import heapq as hq
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

  L = []
  for s, t, x in STX:
    L.append([x, s - x, t - x])

  L.sort(key = lambda x: x[1])
  q = []
  push = hq.heappush
  pop = hq.heappop
  cnt = 0
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      push(q, L[cnt])
      cnt += 1
    t = pop(q)
    while t[2] <= D[i]:
      if q == []:
        print(-1)
        break
      t = pop(q)
    else:
      print(t[0])
    push(q, t)

main()

### FIXED CODE ###

import heapq
def main():
  N, Q = list(map(int, input().split()))
  STX = tuple(list(map(int, input().split())) for _ in range(N))
  D = tuple([int(input()) for _ in range(Q)])

  L = []
  for s, t, x in STX:
    L.append((x, s - x, t - x))

  L.sort(key = lambda x: x[1])
  q = []
  cnt = 0
  push = heapq.heappush
  pop = heapq.heappop
  t = []
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      if t != []:
        push(q, t)
        t = []
      push(q, L[cnt])
      cnt += 1
    if t != [] and t[2] > D[i]:
      print(t[0])
    else:
      while q != []:
        t = pop(q)
        if t[2] > D[i]:
          print(t[0])
          break
      else:
        t = []
        print(-1)

main()
### BUGGY CODE ###

n = int(input())
a = [int(an) for an in input().split()]
q = int(input())

a_sum = sum(a)
for i in range(q):
    stdins = input().split()
    b = int(stdins[0])
    c = int(stdins[1])
    for j in range(n):
        if a[j] == b:
            a[j] = c
            a_sum = a_sum - b + c
    print(a_sum)


### FIXED CODE ###

n = int(input())
a = input().split()

a_cnts = {}
a_sum = 0
for an in a:
    if an in a_cnts.keys():
        a_cnts[an] += 1
    else:
        a_cnts[an] = 1
    a_sum += int(an)

q = int(input())

for i in range(q):
    (b, c) = input().split()

    if b in a_cnts.keys():
        hit_cnt = a_cnts[b]
        del a_cnts[b]
        if c in a_cnts.keys():
            a_cnts[c] += hit_cnt
        else:
            a_cnts[c] = hit_cnt
        a_sum += (int(c) - int(b))*hit_cnt

    print(a_sum)
### BUGGY CODE ###

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

a.sort()

result = 0
mod = 10**9+7

def solve(x, y):
    if x == 0:
        return 1
    else:
        x = min(x, y-x)
        r = 1
        for i in range(y-x+1, y+1):
            r *= i
            r %= mod
        for i in range(1, x+1):
            r *= pow(i, mod-2, mod)
            r %= mod
        return r


if k==1:
    print(0)
else:
    result = 0
    for i in range(n-k+1):
        result += (a[n-i-1]-a[i])*solve(k-1, n-i-1)
        result %= mod
    print(result)

### FIXED CODE ###

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

a.sort()

result = 0
mod = 10**9+7

 
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7 #出力の制限
n = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, n+1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


if k==1:
    print(0)
else:
    result = 0
    for i in range(N-k+1):
        result += (a[N-i-1]-a[i])*cmb(N-1-i, k-1)
        result %= mod

    print(result%mod)
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
count = 1

for i in range(1,N):
    flag = True
    for j in range(i):
        if P[j] < P[i]:
            flag = False
            break
    if flag:
        count += 1

print(count)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
count = 0
min_P = P[0]

for i in range(0,N):
    if P[i] < min_P:
        min_P = P[i]
    if min_P >= P[i]:
        count += 1

print(count)
### BUGGY CODE ###

from collections import defaultdict

def main():
    N, M = map(int, input().split())
    a = [input().split() for _ in range(M)]
    fin = []
    wa_count = defaultdict(lambda:0)
    ac, wa = 0, 0

    for q_no, ans in a:
        if q_no not in fin:
            if ans == "AC":
                fin.append(q_no)
                ac += 1
                wa += wa_count.get(q_no, 0)
            else:
                wa_count[q_no] += 1
    
    print(ac, wa)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict

def main():
    N, M = map(int, input().split())
    a = [input().split() for _ in range(M)]
    ac_count = [0] * (N + 1)
    wa_count = defaultdict(lambda:0)
    ac, wa = 0, 0

    for q_no, ans in a:
        q_no = int(q_no)
        if ac_count[q_no] == 0:
            if ans == "AC":
                ac_count[q_no] = 1
                ac += 1
                wa += wa_count.get(q_no, 0)
            else:
                wa_count[q_no] += 1
    
    print(ac, wa)

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

def prime(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes
pp=prime(10**3)
p=[]
for i in range(2,1001):
  if pp[i]:
    p.append(i)
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

g=a[0]
for i in a[1:]:
  g=gcd(g,i)
if g==1:
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i] and i!=1:
      f=False
      break
    mm[i]=1
    for j in range(168):
      if i%p[j]==0:
        if mm[p[j]] and i!=p[j]:
          f=False
          break
        mm[p[j]]=1
        if mm[i//p[j]] and i//p[j]!=p[j] and i!=p[j]:
          f=False
          break
        mm[i//p[j]]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")
      


### FIXED CODE ###

def prime(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes
pp=prime(10**3)
p=[]
for i in range(2,1001):
  if pp[i]:
    p.append(i)
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

g=a[0]
for i in a[1:]:
  g=gcd(g,i)
if g==1:
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i] and i!=1:
      f=False
      break
    mm[i]=1
    si=i**0.5
    for j in range(168):
      if p[j]>si:
        break
      if i%p[j]==0 and i!=p[j]:
        if mm[p[j]]:
          f=False
          break
        mm[p[j]]=1
        t=i//p[j]
        if mm[t] and t!=p[j]:
          f=False
          break
        mm[t]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")
### BUGGY CODE ###

n = int(input())
A = [*map(int,input().split())]
# print(n,A)
ans = 1
for a in A:
    ans *=a
if ans > 10**18: ans = -1
print(ans)


### FIXED CODE ###

n = int(input())
A = [*map(int,input().split())]
A.sort()
# print(n,A)
ans = 1
for a in A:
    if a == 0:
        ans = 0
        break
    ans *= a
    if ans > 10**18:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

N = int(input())
S = []
for _ in range(N):
    s = str(input())
    if s not in S:
        S.append(s)

print(len(S))

### FIXED CODE ###

N = int(input())
S = []
for _ in range(N):
    s = str(input())
    S.append(s)
S1 = sorted(S)
counter=1
for i in range(N-1):
    if S1[i]!=S1[i+1]:
        counter+=1
print(counter)
### BUGGY CODE ###

import collections

n=int(input())
li = list(map(int,input().split()))
cli = collections.Counter(li)
cli_values = tuple(cli.values())

count = 0

for cli_value in cli_values:
    if cli_value > 1:
        count += (cli_value * (cli_value-1))//2

for k in range(n):
    tmp = li.count(li[k])
    answer = count - (tmp * (tmp-1))//2 + ((tmp-1) * (tmp-2))//2
    print(answer)

### FIXED CODE ###

import collections

n=int(input())
li = list(map(int,input().split()))
cli = collections.Counter(li)
cli_values = tuple(cli.values())

count = 0

for cli_value in cli_values:
    if cli_value > 1:
        count += (cli_value * (cli_value-1))//2

for k in range(n):
    tmp = cli[li[k]]
    answer = count - (tmp * (tmp-1))//2 + ((tmp-1) * (tmp-2))//2
    print(answer)
### BUGGY CODE ###

n, q = map(int, input().split())
#n = 4
#q = 3

ans = [0]*n
ki = {}
for i in range(1,n+1):
    ki[i] = []

#z = ["1 2", "2 3", "2 4"]

for i in range(n-1):
    e = list(map(int, input().split()))
    #e = list(map(int, z[i].split()))
    ki[e[0]].append(e[1])

#print(ki)

def df(graph, start, point):
    stack = [start]
    visited = []
    while stack:
        v = stack.pop(0)
        ans[v - 1] += point
        if v not in visited:
            visited.append(v)
            stack = graph.get(v, []) + stack

#y = ["2 10", "1 100", "3 1"]
for i in range(q):
    p = list(map(int, input().split()))
    #p = list(map(int, y[i].split()))
    df(ki, p[0], p[1])

print(' '.join(list(map(str, ans))))
#for n in ans:
#    print(n, end=" ")



### FIXED CODE ###

import sys

def main():
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n, q = map(int, input().split())
    #n, q = map(int, "4 3".split())
    g = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        #a, b = map(int, ["1 2", "2 3", "2 4"][i].split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)


    add = [0] * n
    for i in range(q):
        p, v = map(int, input().split())
        #p, v = map(int, ["2 10", "1 100", "3 1"][i].split())
        #dfs(p-1, v)
        add[p-1] += v

    ans = [0] * n
    def dfs(v,p,value): #p: parent of v
        value += add[v]
        ans[v] = value
        for c in g[v]:
            if c == p: continue
            dfs(c,v,value)
    dfs(0, -1, 0)
    """
    def dfs(start, point):
        stack = [start]
        while stack:
            x = stack.pop()
            ans[x] += point
            stack += g[x]
    """

    print(' '.join(map(str, ans)))

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

#if a is goal, decrease after a
import copy

def goal(win_n,*list_d):
	ans_1=0             #case_number
	if len(list_d)==1:
		list_d=list_d[0]
	if list_d==[]:
		return 1
	for i in range(win_n):
		for j in range(i):
			if list_d[j]<=2*j:
				break
		else:
			List_d=copy.deepcopy(list_d)
			del List_d[i]
			ans_1+=goal(win_n-1,List_d)
	return ans_1

N=int(input())
List=[int(i) for i in input().split()]

ans=goal(N,List)
print(ans)

### FIXED CODE ###

N=int(input())
x=[int(i) for i in input().split()]
ans=1
index=0
advance=0
devide=10**9+7

while True:
	if 2*(index-advance)+1 <= x[index]:
		index+=1
		if index==N:
			break
	else:
		ans*=(index-advance+1)#need concern
		ans%=devide
		index+=1
		advance+=1
		if index==N:
			break
for i in range(index-advance,0,-1):
	ans*=i
	ans%=devide
print(ans)