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

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    s=['Vacant','Male', 'Female']
    right=0
    left=n
    sr=input("0")
    if sr=="Vacant":
        print(0)
        sys.exit()
    if input(str(n-1))=="Vacant":
        print(n-1)
        sys.exit()
    while right-left>1:
        mid=(left-right)//2
        x=input(str(mid))
        if x=="Vacant":
            print(str(mid))
            sys.exit()
        if ((left-right)%2==0 and x!=sr) or (n2%2==1 and x==sr):
            left=mid
        else:
            right=mid
            sr=x
    print(str(right))


if __name__=='__main__':
    main()

### FIXED CODE ###

N=int(input())
l,r=0,N
print(0)
s=input()
ls=s
if s!='Vacant':
    for i in range(19):
        x=l+(r-l)//2
        print(x)
        s=input()
        if s=='Vacant':
            break
        elif (x-l)%2==0 and s==ls or (x-l)%2==1 and s!=ls:
            l=x
            ls=s
        else:
            r=x
### BUGGY CODE ###

S = input()
n = len(S)
mod = (10**9 + 7)

A = [0] * n
C = [0] * n
Q = [0] * n
Bi = []
Qi = []

for i, s in enumerate(S):
    if s == 'A':
        A[i] = 1
    elif s == 'B':
        Bi.append(i)
    elif s == 'C':
        C[i] = 1
    else:
        Q[i] = 1
        Qi.append(i)

for i in range(1, n):
    A[i] += A[i - 1]
    C[i] += C[i - 1]
    Q[i] += Q[i - 1]

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = divmod(n, 2)
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

from itertools import chain
ans = 0
for b in chain(Bi, Qi):
    if b == 0 or n - 1 <= b: continue
    ai = A[b - 1]
    qa = Q[b - 1]
    a = (ai * mod_pow(3, qa, mod)) % mod
    if qa > 0:
        a += (mod_pow(3, qa - 1, mod) * qa) % mod

    ci = C[b]
    qc = Q[b]
    lc = C[n - 1] - ci
    lqc = Q[n - 1] - qc
    c = (lc * mod_pow(3, lqc, mod)) % mod
    if lqc > 0:
        c += (mod_pow(3, lqc - 1, mod) * lqc) % mod
    
    ans += (a * c) % mod

print(ans % mod)

### FIXED CODE ###

S = input()
n = len(S)
mod = (10**9 + 7)

dp = [[0] * 4 for _ in range(n + 1)]

dp[n] = [0, 0, 0, 1]
for i in range(n-1, -1, -1):
    if S[i] == '?':
        dp[i][3] =  dp[i+1][3] * 3 % mod
        dp[i][2] = (dp[i+1][2] * 3 + dp[i+1][3]) % mod
        dp[i][1] = (dp[i+1][1] * 3 + dp[i+1][2]) % mod
        dp[i][0] = (dp[i+1][0] * 3 + dp[i+1][1]) % mod
    elif S[i] == 'C':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] = (dp[i+1][2] + dp[i+1][3]) % mod
        dp[i][1] =  dp[i+1][1] % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'B':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] =  dp[i+1][2] % mod
        dp[i][1] = (dp[i+1][1] + dp[i+1][2]) % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'A':
        dp[i][3] =  dp[i+1][3]
        dp[i][2] =  dp[i+1][2]
        dp[i][1] =  dp[i+1][1]
        dp[i][0] = (dp[i+1][0] + dp[i+1][1]) % mod
print(dp[0][0])
### BUGGY CODE ###

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *A, = map(int, input().split())

    dp = [[0] * 3 for _ in range(S + 1)]
    dp[0][0] = 1

    for x in A:
        for s in range(S, 0, -1):
            dp[s][2] = (dp[s][2] + dp[s][1]) % MOD
            if s - x >= 0:
                v = dp[s - x][1] + dp[s - x][0]
                dp[s][1] = (dp[s][1] + v) % MOD
                dp[s][2] = (dp[s][2] + v) % MOD

        dp[0][1] = (dp[0][1] + 1) % MOD
        dp[0][2] = (dp[0][2] + dp[0][1] + 1) % MOD

    print(dp[S][2])


if __name__ == '__main__':
    main()

#             dp[i + 1][s][0] = (dp[i + 1][s][0] + dp[i][s][0]) % MOD
#             dp[i + 1][s][1] = (dp[i + 1][s][1]
#                                + dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD
#             dp[i + 1][s][2] = (dp[i + 1][s][2]
#                                + dp[i][s][2] +
#                                dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD

#     for i, x in enumerate(A):
#         dp[i + 1][0][0] = dp[i][0][0]
#         for s in range(S, -1, -1):
#             dp[i + 1][s][1] = (dp[i][s][1] + dp[i][s][0]) % MOD
#             dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1] + dp[i][s][0]) % MOD
#
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD

#         dp[i + 1][0][0] = dp[i][0][0]
#         dp[i + 1][0][1] = (dp[i][0][1] + dp[i][0][0]) % MOD
#         dp[i + 1][0][2] = (dp[i][0][2] + dp[i][0][1] + dp[i][0][0]) % MOD
#         for s in range(S, 0, -1):
#             dp[i + 1][s][1] = dp[i][s][1] % MOD
#             dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1]) % MOD
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        if x > S: continue
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


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

N = int(input())
A = [0] * N
A = list(map(int,input().split()))

ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += A[i] * A[j]
print(ans%(10**9+7))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0] * (N+1)

# 累積和を使う
for i in range(1,N+1):
    B[i] = A[i-1]+B[i-1]
# 累積和の配列完成
# print(B) 

ans = 0
MOD = 10**9+7
for i in range(N):
    ans += A[i] * (B[N] - B[i+1])
    ans %= MOD
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()

a = [a[i] for i in range(N) if a[i]<K]
a.reverse()
N = len(a)
ans = N
dp = [False]*K
dp[0] = True
Smax = 0
for i,a_ in enumerate(a):
    if Smax + a_ >= K:
        ans = N-i-1
    updated = False
    for j in range(min(Smax,K-a_-1),-1,-1):
        if dp[j]:
            dp[j+a_]=True
            if not updated:
                Smax = max(Smax,j+a_)
                updated = True

print(ans)

### FIXED CODE ###

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

def f(N,K,a):
    a.sort()
    if a[0] >= K:
        print(0)
        exit()

    a = [a[i] for i in range(N) if a[i]<K]
    N = len(a)
    ans = N
    dp = [False]*K
    dp[0] = True
    Smax = 0
    for i,a_ in reversed(list(enumerate(a))):
        if Smax + a_ >= K:
            ans = i
        updated = True
        for j in range(min(Smax,K-a_-1),-1,-1):
            if dp[j]:
                dp[j+a_]=True
                if updated:
                    Smax = max(Smax,j+a_)
                    updated = False
    return ans

print(f(N,K,a))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
prime = 10 ** 9 + 7
max_digit = len(bin(max(A))[2:])
A_bin = list(map(lambda x: bin(x)[2:].zfill(max_digit), A))
zero = [0] * max_digit
one = [0] * max_digit

for num in A_bin:
    for digit in range(max_digit):
        if num[-(digit + 1)] == '0':
            zero[digit] += 1
        else:
            one[digit] += 1

for digit in range(max_digit):
    ans += (((zero[digit] * one[digit]) % prime) * pow(2, digit, prime)) % prime
    ans %= prime

print(ans)


### FIXED CODE ###

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
ans = 0
MOD = 10 ** 9 + 7

for digit in range(60):
    one = np.count_nonzero((A >> digit) & 1)
    ans += (one * (N - one) * pow(2, digit, MOD)) % MOD
    ans %= MOD

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

def main():
    N=int(input())
    A=[int(_) for _ in input().split()]
    ans = sum(A)-A[0]
    for i in range(N):
        ans = min(ans, abs(sum(A[:i]) - sum(A[i:])))
    print(ans)

main()

### FIXED CODE ###

def main():
    N=int(input())
    A=[int(_) for _ in input().split()]
    left=0
    right=sum(A)
    ans=right
    for i in range(N):
        left+=A[i]
        right-=A[i]
        ans = min(ans, abs(left-right))
    print(ans)

main()
### BUGGY CODE ###

s = input()[::-1]
n = len(s)
amari = [0]*2019
amari[0] = 1

temp = 0
for i in range(n):
    temp += int(s[i])*10**i
    amari[temp%2019] += 1

ans = 0
frag = False
for i in amari:
    ans += i*(i-1)/2

print(int(ans))



### FIXED CODE ###

s = input()[::-1]
n = len(s)
amari = [0]*2019
amari[0] = 1

temp = 0
d = 1
for char in s:
    temp += int(char)*d
    temp %= 2019
    d *= 10
    d %= 2019  
    amari[temp] += 1

ans = 0
for i in amari:
    ans += i*(i-1)/2

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



def submit():
    n = int(input())
    s = input()

    r_cnt = [0 for _ in range(n)]
    g_cnt = [0 for _ in range(n)]
    b_cnt = [0 for _ in range(n)]

    for i in reversed(range(n)):
        if s[i] == 'R':
            r_cnt[i] = 1
        if s[i] == 'G':
            g_cnt[i] = 1
        if s[i] == 'B':
            b_cnt[i] = 1

    for i in reversed(range(1, n)):
        r_cnt[i - 1] += r_cnt[i]
        g_cnt[i - 1] += g_cnt[i]
        b_cnt[i - 1] += b_cnt[i]


    ans = 0
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            if s[i] == s[j]:
                continue
            dist = j - i
            if {s[i], s[j]} == {'R', 'G'}:
                ans += b_cnt[j + 1]
                if j + dist < n and s[j + dist] == 'B':
                    ans -= 1
            elif {s[i], s[j]} == {'R', 'B'}:
                ans += g_cnt[j + 1]
                if j + dist < n and s[j + dist] == 'G':
                    ans -= 1
            else:
                ans += r_cnt[j + 1]
                if j + dist < n and s[j + dist] == 'R':
                    ans -= 1
    print(ans)


submit()    


### FIXED CODE ###



def submit():
    n = int(input())
    s = input()

    r_cnt = [0 for _ in range(n)]
    g_cnt = [0 for _ in range(n)]
    b_cnt = [0 for _ in range(n)]

    for i in reversed(range(n)):
        if s[i] == 'R':
            r_cnt[i] = 1
        if s[i] == 'G':
            g_cnt[i] = 1
        if s[i] == 'B':
            b_cnt[i] = 1

    for i in reversed(range(1, n)):
        r_cnt[i - 1] += r_cnt[i]
        g_cnt[i - 1] += g_cnt[i]
        b_cnt[i - 1] += b_cnt[i]


    ans = 0
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            if s[i] == s[j]:
                continue
            dist = j - i
            if {s[i], s[j]} == {'R', 'G'}:
                ans += b_cnt[j + 1]
                if j + dist < n and s[j + dist] == 'B':
                    ans -= 1
            elif {s[i], s[j]} == {'R', 'B'}:
                ans += g_cnt[j + 1]
                if j + dist < n and s[j + dist] == 'G':
                    ans -= 1
            else:
                ans += r_cnt[j + 1]
                if j + dist < n and s[j + dist] == 'R':
                    ans -= 1
    print(ans)


submit()
### BUGGY CODE ###

def main():
  import heapq as hq
  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 = []
  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
    while q != []:
      t = pop(q)
      if t[2] > D[i]:
        print(t[0])
        push(q, t)
        break
    else:
      print(-1)

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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
ns = [[] for _ in range(n)]
for _ in range(m):
    u,v = map(int, input().split())
    ns[u].append(v)
import networkx as nx
g = nx.DiGraph()
for i in range(n):
    g.add_node(i)
for i in range(n):
    for j in ns[i]:
        g.add_edge(i,j)
comp = list(nx.strongly_connected_components(g))
print(len(comp))
for item in comp[::-1]:
    print(len(item), " ".join(map(str, item)))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
ns = [[] for _ in range(n)]
for _ in range(m):
    u,v = map(int, input().split())
    ns[u].append(v)
def scc():
    preorder = {}
    lowlink = {}
    seen = [False]*n
    scc_queue = []
    i = 0  # Preorder counter
    ans = []
    for source in range(n):
        if seen[source]:
            continue
        queue = [source]
        while queue:
            v = queue[-1]
            if v not in preorder:
                i = i + 1
                preorder[v] = i
            done = True
            for w in ns[v]:
                if w not in preorder:
                    queue.append(w)
                    done = False
                    break
            if done:
                lowlink[v] = preorder[v]
                for w in ns[v]:
                    if seen[w]:
                        continue
                    if preorder[w] > preorder[v]:
                        lowlink[v] = min([lowlink[v], lowlink[w]])
                    else:
                        lowlink[v] = min([lowlink[v], preorder[w]])
                queue.pop()
                if lowlink[v] == preorder[v]:
                    scc = {v}
                    seen[v] = True
                    while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
                        k = scc_queue.pop()
                        scc.add(k)
                        seen[k] = True
                    ans.append(scc)
                else:
                    scc_queue.append(v)
    return ans
comp = scc()
print(len(comp))
for item in reversed(comp):
    print(len(item), " ".join(map(str, item)))
### BUGGY CODE ###

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

m = S.count('W')
x = 0

for i in range(N):
    x = S.count('E')
    if x < m:
        m = x

    if S[i] == 'W':
        S[i] = 'E'
    else:
        S[i] = 'W'

print(m)


### FIXED CODE ###

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

m = N
x = S.count('E')

for i in S:
    if i == 'E':
        x = x - 1

    if x < m:
        m = x

    if i == 'W':
        x = x + 1

print(m)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
broken = [i in a for i in range(n)]
mod = 1000000007
dp = [0 for _ in range(n+2)]
dp[n] = 1
for i in range(n)[::-1]:
    if(broken[i]):
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod
print(dp[0])

### FIXED CODE ###

n, m = map(int, input().split())
broken = [0 for _ in range(n)]
for _ in range(m):
    broken[int(input())] = 1
mod = 1000000007
dp = [0 for _ in range(n+2)]
dp[n] = 1
for i in range(n)[::-1]:
    if(broken[i]):
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod
print(dp[0])
### BUGGY CODE ###

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


MOD = 1000000007

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


seen = [False] * N

numer = 0
pow2 = [1] * (N + 1)
for i in range(N):
    pow2[i + 1] = pow2[i] * 2 % MOD

def dfs1(v):
    global numer
    seen[v] = True
    nodes = []
    childs = 0
    for nv in G[v]:
        if not seen[nv]:
            nodes.append(dfs1(nv) + 1)
            childs += nodes[-1]
    if v != 0:
        nodes.append(N - childs - 1)
    if len(nodes) > 1:
        this_numer = pow2[N - 1] - (sum(pow2[n] - 1 for n in nodes) + 1)
        numer = (numer + this_numer) % MOD
    return childs


dfs1(0)

denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)




### FIXED CODE ###

from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


MOD = 1000000007
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

pow2 = [1] * (N + 1)
for i in range(N):
    pow2[i + 1] = pow2[i] * 2 % MOD

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            c = nums[nv] + 1
            nums[v] += c
            tmp += pow2[c] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)
### BUGGY CODE ###

Q, H, S, D = map(int, input().split())
N = int(input())

ans = 10**9
for w in range(N//2+1):
    for z in range(N-2*w+1):
        for y in range(2*(N-2*w-z)+1):
            x = 4 * (N - 2*w - z - y//2)
            ans = min(ans, Q*x + H*y + S*z + D*w)

print(ans)


### FIXED CODE ###

Q, H, S, D = map(int, input().split())
N = int(input())

two_l = min(8*Q, 4*H, 2*S, D)
one_l = min(4*Q, 2*H, S)

ans = (N//2)*two_l + (N%2)*one_l
print(ans)
### BUGGY CODE ###

import numpy as np

MOD=10**9+7
N,x=map(int,input().split())
 
a=list(map(int,input().split()))
a.sort()
a.reverse()
table=np.arange(x+1)


for i in range(N-1,-1,-1):
	tmp=table.copy()
	for j in range(x+1):
		table[j]=( tmp[j]*(N-1-i) + tmp[j%a[i]] ) % MOD
 
print(int(table[x]))

### FIXED CODE ###

import math

def cul(i,x):
    if tmp[i][x]==-1:
        tmp[i][x]=( cul(i+1,x)*(N-1-i) + cul(i+1,x%a[i]) )%MOD
    return tmp[i][x]

MOD=10**9+7
N,x=map(int,input().split())

a=list(map(int,input().split()))
a.sort(reverse=True)
tmp= [[-1 for j in range(x+1)] for i in range(N)] + [[j for j in range(x+1)]]

print(cul(0,x))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
A = [int(input()) for i in range(m)]
mod = 10**9+7
memo={}
memo[1]=1
memo[0]=1

def fib(n):
  if n in A:
  	memo[n]=0
  	return memo[n]
  if n not in memo:
    memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

print(fib(n)%mod)

### FIXED CODE ###

n,m=map(int,input().split())
A = [int(input()) for i in range(m)]
ls =[-1]*(n+1)
ls[0]=ls[1]=1
mod = 10**9+7
for a in A:
	ls[a]= 0

for i in range(2,n+1):
	if ls[i]==-1:
		ls[i]= ls[i-1]+ls[i-2]
print(ls[-1]%mod)
### BUGGY CODE ###

n,m = map(int,input().split())
ls = [[int(x) for x in input().split()] for _ in range(m)]

cnt = [[0] for _ in range(n+1)]

for i in range(m):
    idx = ls[i][0]
    cnt[idx].append(ls[i][1])

for i in range(n+1):
    cnt[i].sort()


for i in range(m):
    idx = ls[i][0]
    print("{:06d}{:06d}".format(idx,cnt[idx].index(ls[i][1])))

### FIXED CODE ###

n,m = map(int,input().split())
ls = [[] for _ in range(n+1)]

for i in range(m):
    a,b = map(int,input().split())
    ls[a].append((b,i))
ans = [None]*m
for i,l in enumerate(ls):
    l.sort()
    for j,(a,b) in enumerate(l):
        ans[b]= "{:06d}{:06d}".format(i,j+1)
for i in range(m):
    print(ans[i])
### BUGGY CODE ###

N = int(input())

count = [0 for _ in range(200000)]
line = [int(i) for i in input().split()]
index = []

for i in line:
	# if count[i] == 0:
		# index.append(i)
	count[i] += 1


for i in line:
	count[i] -= 1
	result = 0
	for j in range(200000):
		result += (count[j]*(count[j]-1))//2
	count[i] += 1
	print(result) 


### FIXED CODE ###

N = int(input())

count = [0 for _ in range(200000)]
line = [int(i) for i in input().split()]
pattern = [0 for _ in range(200000)]
sum = 0
# index = []

for i in line:
	# if count[i] == 0:
		# index.append(i)
	count[i] += 1

for num in count:
	sum += (num*(num-1))//2



for i in line:
	if count[i] > 2:
		result = sum - (count[i]-1) 
	elif count[i] == 2:
		result = sum - 1
	elif count[i] == 1:
		result = sum
	print(result)
### BUGGY CODE ###

h, w = map(int, input().split())
lst = []
for i in range(h):
    lst.append(list(input()))

R = [[0]*w for _ in range(h)]
L = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if lst[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
        

for i in range(h):
    for j in range(w-1, -1, -1):
        if lst[i][j] == '.':
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1            


for i in range(h):
    for j in range(w):
        if lst[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

for i in range(h-1, -1, -1):
    for j in range(w):
        if lst[i][j] == '.':
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1

ans = 0
x = [[0]*w for _ in range(h)]
for i in range (h):
    for j in range(w):
        x[i][j] = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
    ans = max(ans, max(x[i]))
print(ans) 

### FIXED CODE ###

h, w = map(int, input().split())
lst = []
for i in range(h):
    lst.append(list(input()))

R = [[0]*w for _ in range(h)]
L = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if lst[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
        

for i in range(h):
    for j in range(w-1, -1, -1):
        if lst[i][j] == '.':
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1            


for i in range(h):
    for j in range(w):
        if lst[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

for i in range(h-1, -1, -1):
    for j in range(w):
        if lst[i][j] == '.':
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1

ans = 0
x = [[0]*w for _ in range(h)]
for i in range (h):
    for j in range(w):
        x[i][j] = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
    ans = max(ans, max(x[i]))
print(ans)