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

#C問題
N,Q=map(int,input().split())
S=str(input())
Slist=list(S)
LR=[list(map(int,input().split())) for i in range(Q)]
for i in range(Q):
    karis=Slist[LR[i][0]-1:LR[i][1]]
    n=LR[i][1]-LR[i][0]+1
    count=0
    for j in range(n-1):
        if karis[j] == "A" and karis[j+1] == "C":
            count+=1
    print(count)

### FIXED CODE ###

#C問題  
N,Q=map(int,input().split())
S=str(input())
Slist=list(S)
pile=[0 for i in range(N)]
for i in range(N-1):
    if i == 0:
        pass
    else:
        pile[i]=pile[i-1]
  
    if Slist[i] == "A" and Slist[i+1] == "C":
        pile[i]+=1
pile[-1]=pile[-2]
pile.insert(0,0)
for i in range(Q):
    l,r=map(int,input().split())
    print(pile[r-1]-pile[l-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
t = 0
mod = 10**9+7
for i in range(n):
    t += a[i]*sum(a[i+1:])
print(t%mod)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
t = 0
r = 0
mod = 10**9+7
for i in range(n-1, 0, -1):
    r += a[i]
    t += a[i-1]*r
print(t%mod)
### BUGGY CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    from functools import reduce

    tmp = [2, 4, 6, 8]
    gcdans = reduce(fractions.gcd, tmp)

    # 最小公倍数
    def lcm_base(x, y):
        return (x * y) // math.gcd(x, y)

    def lcm(*numbers):
        return reduce(lcm_base, numbers, 1)

    def lcm_list(numbers):
        return reduce(lcm_base, numbers, 1)

    n = ni()
    a = na()

    lcm = lcm_list(a)

    ans = 0
    for ai in a:
        ans += lcm // ai
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    from functools import reduce

    # 最小公倍数
    def lcm_base(x, y):
        return (x * y) // math.gcd(x, y)

    def lcm_list(numbers):
        return reduce(lcm_base, numbers, 1)

    n = ni()
    a = na()

    lcm = a[0]
    for i in a:
        lcm = lcm // math.gcd(lcm, i) * i
    lcm %= MOD

    ans = 0
    for ai in a:
        ans += lcm * pow(ai, MOD - 2, MOD) % MOD
        ans %= MOD

    print(ans)


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

n = int(input())
s = input()

ans = 0
while s.find('#.') != -1:
    pos = s.find('#.')
    try:
        if s[pos-1] == '#':
            s = s[:pos] + '##' + s[pos+2:]
        elif s[pos+2] == '.':
            s = s[:pos] + '..' + s[pos+2:]
        elif s[pos-2:pos] == '#.':
            s = s[:pos] + '##' + s[pos+2:]
        elif s[pos+2:pos+4] == '#.':
            s = s[:pos] + '..' + s[pos+2:]
        else:
            s = s[:pos] + '##' + s[pos+2:]
        ans += 1
    except:
        a = 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = list(input())
res = 10**9

cta = 0
ctb = 0
a = [0]*n
b = [0]*n
for i in range(n):
    if s[i] == '.':
        cta += 1
    else:
        ctb += 1
    a[i] = cta
    b[i] = ctb
for i in range(n):
    res = min(res,b[i]+a[-1]-a[i])
res = min(res,a[-1],b[-1])
print(res)
### BUGGY CODE ###

def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp = [0 for i in range(t)]
    ls = [[] for i in range(t)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0 and dp[j - f[i][0]] + f[i][1] > dp[j]:
                dp[j] = dp[j - f[i][0]] + f[i][1]
                ls[j] = ls[j - f[i][0]] + [i]
    res = dp[t - 1]
    ll = ls[t - 1]
    fff = [0 for _ in range(n)]
    for sll in ll:
        fff[sll] = 1
    ff = [f[i][1] for i in range(n) if fff[i] == 0]
    if ff:
        return res + max(ff)
    else:
        return res


print(main())


### FIXED CODE ###



def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp1 = [[0 for i in range(t)]for j in range(n+1)]
    dp2 = [[0 for i in range(t)]for j in range(n+1)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0:
                dp1[i+1][j] = max(dp1[i][j - f[i][0]] + f[i][1],dp1[i][j])
            else:
                dp1[i+1][j] = dp1[i][j]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[n-1-i][0] >= 0:
                dp2[i+1][j] = max(dp2[i][j - f[n-1-i][0]] + f[n-1-i][1],dp2[i][j])
            else:
                dp2[i+1][j] = dp2[i][j]

    res = 0
    for i in range(n):
        for j in range(t):
            res = max(res,dp1[i][j]+f[i][1]+dp2[n-1-i][t-1-j])

    return res




print(main())
### BUGGY CODE ###

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

num = 1
pos = 0
count = 0

while pos < len(a_list):
    if num != a_list[pos]:
        del a_list[pos]
        count += 1
    else:
        num += 1
        pos += 1

if len(a_list) == 0:
    print(-1)
else:
    print(count)

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
ans = 0
wait_for = 1
for a in a_list:
    if a == wait_for:
        wait_for += 1
    else:
        ans += 1
if wait_for == 1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
a = [list(map(int,input().split())) for _ in range(2)]
dp = [[1000]*(2**n) for _ in range(51)]
dp[0][0] = 0
for S in range(2**n):
  j = bin(S).count("1")
  for i in range(n):
    if not (S & 1<<i):
      cnt = bin(S)[2:].zfill(n)[n-i:].count("0")
      k = a[(i+j)%2][i]
      for l in range(k+1):
        dp[k][S|1<<i] = min(dp[k][S|1<<i],dp[l][S]+cnt)
ans = min(dp[i][-1] for i in range(51))
if ans == 1000:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n = int(input())
a = [list(map(int,input().split())) for _ in range(2)]
dp = [[1000]*(2**n) for _ in range(51)]
dp[0][0] = 0
for S in range(2**n):
  j = bin(S).count("1")
  cnt = 0
  for i in range(n):
    if not (S & 1<<i):
      k = a[(i+j)%2][i]
      for l in range(k+1):
        dp[k][S|1<<i] = min(dp[k][S|1<<i],dp[l][S]+cnt)
    if not (S&1<<i):
      cnt += 1
ans = min(dp[i][-1] for i in range(51))
if ans == 1000:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

n = int(input())
g=[]
for i in range(n):
    
    g.append(list(map(int,input().split())))
mod=10**9+7
dp=[0]*(1<<n)
dp[0]=1
for i in range(1,1<<n):
    e=bin(i)[2:]
    y=e.count('1')
    for j in range(len(e)):
        if e[-j-1]=='1':
            if g[y-1][j]:
                    dp[i]+=dp[i-(1<<j)]
                    dp[i]%=mod


print(dp[-1])
            
    
    

### FIXED CODE ###

n = int(input())
g=[]
for i in range(n):
    
    g.append(list(map(int,input().split())))
mod=10**9+7
dp=[0]*(2**n)
dp[0]=1
for i in range(1,2**n):
    e=bin(i)[2:]
    y=e.count('1')
    for j in range(len(e)):
        if e[-j-1]=='1':
            if g[y-1][j]:
                    dp[i]+=dp[i-(2**j)]
                    dp[i]%=mod


print(dp[-1]%mod)
### BUGGY CODE ###

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

count = 0
for i in range(k+1):
  for j in range(k+1):
    for l in range(k+1):
      tot = i+j+l
      if s == tot:
        count += 1
print(count)

### FIXED CODE ###

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

count = 0
for i in range(k+1):
  for j in range(k+1):
    l = s-i-j
    if l>=0 and l<=k:
      count +=1
print(count)
### BUGGY CODE ###

S = list(input())

cnt = 0
t = -1
while cnt != t:
    t = cnt
    for i in range(len(S)-1):
        if S[i] == 'B' and S[i+1] == 'W':
            S[i] = 'W'
            S[i+1] = 'B'
            cnt += 1

print(cnt)

### FIXED CODE ###

S = list(input())

cnt = 0
t = 0
for i in range(len(S)):
    if S[i] == 'W':
        cnt += t
    else:
        t += 1

print(cnt)
### BUGGY CODE ###

def main():
    a,b,c = map(int,input().split())
    k = int(input())

    i = 0
    while a >= b:
        a *= 2
        i += 1
    while b >= c:
        b *= 2
        i += 1
    print("Yes" if i <= k else "No")

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    a,b,c = map(int,input().split())
    k = int(input())

    i = 0
    while a >= b:
        b *= 2
        i += 1
    while b >= c:
        c *= 2
        i += 1
    print("Yes" if i <= k else "No")

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

s = int(input())
l = []
l.append(s)
count = 1
while True:
  if count%2 == 1:
    a = l[-1]*3+1
  else:
    a = l[-1]//2
    
  count += 1
  if a in l:
    print(count)
    exit()
  else:
    l.append(a)

### FIXED CODE ###

s = int(input())
l = []
l.append(s)
count = 1
while True:
  if l[-1]%2 == 1:
    a = l[-1]*3+1
  else:
    a = l[-1]//2
    
  count += 1
  if a in l:
    print(count)
    exit()
  else:
    l.append(a)
### BUGGY CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        if (4*h*n-N*n-N*h) == 0:
            continue
        w = N*h*n // (4*h*n-N*n-N*h)
        if w < 1:
            continue
        if w*(4*h*n-N*n-N*h) == N*h*n:
            print(h, n, w)
            exit()


### FIXED CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        if (4*h*n-N*n-N*h) == 0:
            continue
        w = N*h*n // (4*h*n-N*n-N*h)
        if w < 1:
            continue
        if w*(4*h*n-N*n-N*h) == N*h*n:
            print(h, n, w)
            exit()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0]*n
def choose2(n):
    return n * (n - 1) // 2
total = 0
for i in range(1,n+1):
    total += choose2(a.count(i))
for i in range(n):
    ans[i] = total
    ans[i] -= a.count(a[i]) - 1
print(*ans[:], sep='\n')


### FIXED CODE ###

n = int(input())
a = [int(a)-1 for a in input().split()]
cnt = [0]*n
for i in a:
    cnt[i] += 1
total = 0
for i in cnt:
    total += i * (i-1) // 2
for i in a:
    print(total - (cnt[i] - 1))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n,u,v = map(int, input().split())
adjacent_list = [[]for i in range(n+1)]
aoki = [0 for i in range(n+1)]
takahashi = [0 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)

def dfs(node, count,li):
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i, count + 1,li)
def dfs_par(node, count,li):
    global node_par
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            node_par[i] = node
            dfs_par(i, count + 1,li)
        
node_par = [0 for i in range(n+1)]

finished = set()
dfs(u,0,takahashi)

finished = set()
dfs_par(v,0,aoki)

#さかのぼれるとこまで行く
par = u
start = u

while takahashi[par] < aoki[par]:
    start = par
    par = node_par[start]

ans_height = [0 for i in range(n+1)]
finished = set([node_par[start]])
dfs(start,0,ans_height)
print(max(ans_height) + aoki[start] - 1)



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n,u,v = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
aoki = [0 for i in range(n+1)]
takahashi = [0 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)

def dfs(node, count,li):
    global node_par
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            node_par[i] = node
            dfs(i, count + 1,li)
        
node_par = [0 for i in range(n+1)]

finished = set()
dfs(u,0,takahashi)

#辿って親保存しとく
finished = set()
dfs(v,0,aoki)

#さかのぼれるとこまで行く,startがさかのぼれる最大のノーど
par = u
start = u
while takahashi[par] < aoki[par]:
    start = par
    par = node_par[start]

ans_height = [0 for i in range(n+1)]
finished = set([node_par[start]])
dfs(start,0,ans_height)
print(max(ans_height) + aoki[start] - 1)
### BUGGY CODE ###

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

counter = 0

for a in A:
    for b in B:
        if a < b:
            for c in C:
                if b < c:
                    counter = counter + 1
                else:
                    counter = counter
        else:
            counter = counter

print(counter)

### FIXED CODE ###

import bisect

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

A = sorted(A)
C = sorted(C)

counter = 0

for k in range(N):
    i = bisect.bisect_left(A, B[k])
    j = N - bisect.bisect_right(C, B[k])
    counter += i * j

print(counter)
### BUGGY CODE ###

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

for i in range(N):
  Q = input()
  if Q[0] == "1":
    S = S[::-1]
  elif Q[2] == "1":
    S = Q[4] + S
  else:
    S = S + Q[4]

print(S)

### FIXED CODE ###

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

pre = ""
suf = ""
f = 1
for i in range(N):
  Q = input()
  if Q[0] == "1":
    f *= -1
  elif Q[2] == "1":
    if f > 0:
      pre = Q[4] + pre
    else:
      suf = suf + Q[4]
  else:
    if f < 0:
      pre = Q[4] + pre
    else:
      suf = suf + Q[4]

ans = pre + S + suf
if f > 0:
  print(ans)
else:
  print(ans[::-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ac = [0 for i in range(10**6+2)]

a = sorted(a)

for i in a:
    ac[i] +=1

count =0

for i in a:
    if ac[i]>0:
        if ac[i] == 1:
            count += 1
        for j in a:
            if j%i==0 and not ac[j]==0:
                ac[j]=0


print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ac = [0 for i in range(10**6+2)]



for i in a:
    ac[i] +=1
a = sorted(set(a))
count =0

for i in a:
    if ac[i]>0:
        if ac[i] == 1:
            count += 1
        for j in range(i,10**6+2,i):
            if not ac[j]==0:
                ac[j]=0


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

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

ans = [str(A.index(i + 1) + 1) for i in range(N)]

print(*ans)

### FIXED CODE ###

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

ans = [0] * N
for i, a in enumerate(A):
    ans[a - 1] = (i + 1) 

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

n=int(input())
f=[]
for a in range(1,n+1):
    if n%a==0:
        b=n//a
        f.append(max(len(str(a)),len(str(b))))
print(min(f))

### FIXED CODE ###

import math
n=int(input())
f=[]
for a in range(1,math.floor(n**(1/2))+1):
    if n%a==0:
        b=n//a
        f.append(len(str(b)))
print(min(f))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans = 0
N = int(input())
L = []
for x in range(1,N+1):
    for y in range(1,N+1):
       L.append(gcd(x,y))
for x in L:
    for z in range(1,N+1):
        ans += gcd(x,z)
print(ans) 

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans = 0
N = int(input())
L = []
s_dict = {}
for x in range(1,N+1):
    for y in range(1,N+1):
       if(x == y):
           L.append(x)
           s_dict[(x,y)] = x
       elif(x % y == 0):
           L.append(y)
           s_dict[(x,y)] = y
       elif(y % x == 0):
           L.append(x)
           s_dict[(x,y)] = x
       else:
           tmp = gcd(x,y)
           L.append(tmp)
           s_dict[(x,y)] = tmp

for x in L:
    for z in range(1,N+1):
        ans += s_dict[(x,z)]
        
print(ans)
### BUGGY CODE ###

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

def main():
    N,M=map(int,input().split())
    key=[]
    for i in range(0,M):
        a,b=map(int,input().split())
        c=list(map(int,input().split()))
        s=sum(2**(c[j]-1) for j in range(0,b))
        key.append(s*(10**6)+a)


    node=2**N
    djk=Dijkstra(node)
    for i in range(0,M):
        for j in range(0,node):
            s=key[i]//(10**6)
            a=key[i]%(10**6)
            djk.add(j,s|j,a)

    d=djk.shortest_path(0)
    if d[node-1]==10**15:
        print(-1)
    else:
        print(d[node-1])


if __name__=="__main__":
    main()


### FIXED CODE ###

N,M=map(int,input().split())
key=[]
cost=[]
for i in range(0,M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    s=sum(2**(c[j]-1) for j in range(0,b))
    key.append(s)
    cost.append(a)

node=2**N

dp=[[10**10 for i in range(0,node)] for j in range(0,M)]

for i in range(0,M):
    dp[i][node-1]=0
#i:何番までか j:手に入れた鍵
for i in range(0,M):
    for j in range(1,node):
        k=node-1-j
        if i==0:
            if k|key[0]==node-1:
                dp[0][k]=cost[0]
        else:
            dp[i][k]=min(dp[i-1][k],dp[i-1][k|key[i]]+cost[i])

if dp[M-1][0]>=10**10:
    print(-1)
else:
    print(dp[M-1][0])
### BUGGY CODE ###

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

### FIXED CODE ###

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

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

p = 1
points = [p]
for _ in range(N):
    p = A[p]
    if p in points:
        break
    points.append(p)

idx = points.index(p)

if idx > K:
    print(points[K])
    exit()

head = points[:idx]
cycle = points[idx:]

print(cycle[(K - len(head)) % len(cycle)])

### FIXED CODE ###

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

p = 1
points = [p]
visited = set([p])

for _ in range(N):
    p = A[p]
    if p in visited:
        break
    points.append(p)
    visited.add(p)

idx = points.index(p)

if idx > K:
    print(points[K])
    exit()

cycle = points[idx:]

print(cycle[(K - idx) % len(cycle)])
### BUGGY CODE ###

import math
from functools import reduce
num = int(input())
ans = 0
for i in range(1, num + 1):
    for j in range(1, num + 1):
        for k in range(1, num + 1):
            ans += math.gcd(math.gcd(i, j), k)
print(ans)

### FIXED CODE ###

import math
num = int(input())
ans = 0
for i in range(1, num + 1):
    for j in range(1, num + 1):
        tmp = math.gcd(i, j)
        for k in range(1, num + 1):
            ans += math.gcd(tmp, k)

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

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

flg=1
count=0
while True:
    for i in A: #全て偶数か確かめる
        if i%2==1:
            break
    if flg==1:
        for i in A:
            i=i//2
        count+=1
    else:
        break
print(count)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
 
flg=1
count=0
while True:
    for i in A: #全て偶数か確かめる
        if i%2==1:
            flg=0
            break

    if flg==1:
        for i in range(N):
            A[i]=A[i]//2
        count+=1
    else:
        break
print(count)
### BUGGY CODE ###

input()
S=list(map(int,input().split()))
ans=0
for x in set(S):
    cnt=S.count(x)
    ans+=cnt-x*(cnt>=x)
print(ans)

### FIXED CODE ###

from collections import Counter
N, *A = map(int, open(0).read().split())
print(sum(c - x * (c >= x) for x, c in Counter(A).items()))
### BUGGY CODE ###

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

queue = []
ans = 0
popAt = -1
for i in range(N):
    temp = []
    while A[i] > 0:
        temp.append(A[i] & -A[i])
        A[i] -= A[i] & -A[i]
    for j in range(popAt + 1,len(queue)):
        if len(set(queue[j][1] + temp)) < len(queue[j][1]) + len(temp):
            ans += i - queue[j][0]
            popAt = j
        else:
            queue[j][1] = list(set(queue[j][1] + temp))
    queue.append([i,temp])

popAt += 1
z = ((N - popAt) * (N - popAt + 1)) // 2
print(ans+z)


### FIXED CODE ###

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

cur = A[0]
ans = 0
rp = 1
for lp in range(N):
    while rp < N and cur & A[rp] == 0:
        cur += A[rp]
        rp += 1
    ans += rp - lp
    cur -= A[lp]
    
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A_set = list(set(A))
Ad = {a_set: A.count(a_set) for a_set in A_set}
Ad_score = {}
for ad_key, ad_value in Ad.items():
  Ad_ = Ad.copy()
  Ad_[ad_key] -= 1
  Ad_score[ad_key] = sum([(x>1) * x * (x-1) / 2 for x in list(Ad_.values())])

A_out = [str(int(Ad_score[a])) for a in A]
print('\n'.join(A_out))

### FIXED CODE ###

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

# A_set = list(set(A))
# Ad = {a_set:A.count(a_set) for a_set in A_set}
Ad = {}
for i in A:
  if not i in Ad:
    Ad[i]=0
  Ad[i] += 1

score_sum = sum([x*(x-1)/2 for x in list(Ad.values())])

for a in A:
    print(int(score_sum - (Ad[a] - 1)))