Harryxun/stf_run huggingface dataset:
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def popcorn(i,k):
    num = 0
    ii = i
    while ii > 0:
        if ii&1:
            num += 1
        ii //= 2
    if i%num:
        return popcorn(i%num,k+1)
    else:
        return k+1

def main():
    n = int(ipt())
    x = list(map(int,list(input())))
    si = sum(x)
    su = si+1
    sd = si-1
    amu = 0
    amd = 0
    n2u = [1]
    if si == 2:
        n2d = [0]
    else:
        n2d = [1]
    for i in x[::-1]:
        if i:
            amu = (amu+n2u[-1])%su
            amd = (amd+n2d[-1])%sd
        n2u.append((n2u[-1]*2)%su)
        n2d.append((n2d[-1]*2)%sd)
    for i,xi in enumerate(x):
        if xi:
            ni = (amd-n2d[-2-i])%sd
            if si == 1:
                print(0)
            elif ni == 0:
                print(1)
            else:
                print(popcorn(ni,1))
        else:
            ni = (amu+n2u[-2-i])%su
            if ni == 0:
                print(1)
            else:
                print(popcorn(ni,1))


    return None

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def popcorn(i,k):
    num = 0
    ii = i
    while ii > 0:
        if ii&1:
            num += 1
        ii //= 2
    if i%num:
        return popcorn(i%num,k+1)
    else:
        return k+1

def main():
    n = int(ipt())
    x = list(map(int,list(input())))
    si = sum(x)
    su = si+1
    sd = max(1,si-1)
    amu = 0
    amd = 0
    n2u = [1]
    if si == 2:
        n2d = [0]
    else:
        n2d = [1]
    for i in x[::-1]:
        if i:
            amu = (amu+n2u[-1])%su
            amd = (amd+n2d[-1])%sd
        n2u.append((n2u[-1]*2)%su)
        n2d.append((n2d[-1]*2)%sd)
    for i,xi in enumerate(x):
        if xi:
            ni = (amd-n2d[-2-i])%sd
            if si == 1:
                print(0)
            elif ni == 0:
                print(1)
            else:
                print(popcorn(ni,1))
        else:
            ni = (amu+n2u[-2-i])%su
            if ni == 0:
                print(1)
            else:
                print(popcorn(ni,1))


    return None

if __name__ == '__main__':
    main()
a=int(input())

b=list(a)

if(b[0]==9 or b[1]==9):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

a=input()

b=list(a)

b=[int(i) for i in b]

if(b[0]==9 or b[1]==9):
    print("Yes")
else:
    print("No")
a, b = map(int, raw_input().split())
print a*b 2*(a+b)

### FIXED CODE ###

a, b = map(int, raw_input().split())
print a*b, 2*a+2*b
N,M = list(map(int,input().split()))
d = {}
for i in range(N):
	k,l = list(map(int,input().split()))
	d[k] = l

e = sorted(d.items(),key = lambda x: x[0])

a= 0
ans = 0
for i in range(N):
	a += e[i][1]
	if M > a:
		ans += e[i][0]*e[i][1]
	else:
		ans += e[i][0]*(e[i][1]-a+M)
		break

print(ans)

### FIXED CODE ###

N,M = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(N)]
A.sort()

ans = 0
for i in range(N):
	if M > A[i][1]:
		ans += A[i][0]*A[i][1]
		M -= A[i][1]
	else:
		ans += A[i][0]*M
		break

print(ans)
import sys
input = sys.stdin.readline

def main():
	N = int(input())
	a = list(map(int,input().split()))
	ball = []
	ballNum = 0
	f = [0]*N

	for i in reversed(range(1,N)):
		if (sum(f[0::i]) % 2) != (a[i] % 2):
			f[i] = 1
			ball.append(i+1)
			ballNum +=1

	if (sum(f) % 2) != (a[i] % 2):
		f[i] = 1
		ball.append(i+1)
		ballNum +=1

	print(ballNum)
	print(*ball)

if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def sumN(n,N,f):
	total = 0
	i = n
	while i < N:
		total += f[i]
		i += n+1

	if total % 2:
		return 1
	else:
		return 0

def main():
	N = int(input())
	a = list(map(int,input().split()))
	ball = []
	ballNum = 0
	f = [0]*N

	for i in reversed(range(1,N)):
		if sumN(i,N,f) != (a[i] % 2):
			f[i] = 1
			ball.append(i+1)
			ballNum +=1

	if (sum(f) % 2) != (a[0] % 2):
		f[0] = 1
		ball.append(1)
		ballNum +=1

	print(ballNum)
	print(*ball)

if __name__ == "__main__":
	main()
import math
from functools import reduce
from random import randint
import time

n = int(input())

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


def gcd_list(numbers):
    return reduce(math.gcd, numbers)


gcd_l = [0]
gcd_r = []
for i in range(1,n+1):
    a_l = a[:i-1]
    a_r = a[i:]
    if a_l:
        gcd_l.append(gcd_list(a_l))
    if a_r:
        gcd_r.append(gcd_list(a_r))
gcd_r = gcd_r + [0]

ans = 0
for i in range(n):
    if gcd_l[i] == 0:
        gcd = gcd_r[i]
    if gcd_r[i] == 0:
        gcd = gcd_l[i]
    else:
        gcd = math.gcd(gcd_l[i],gcd_r[i])
    ans = max(gcd,ans)

print(ans)

### FIXED CODE ###

import fractions
from functools import reduce

n = int(input())

a = list(map(int,input().split()))
#
# a = [4,8,12,9,16]


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


gcd_l = [a[0]]
gcd_r = [a[-1]]
for i in range(1,n):
    gcd_l.append(fractions.gcd(gcd_l[i-1],a[i]))
    gcd_r.append(fractions.gcd(gcd_r[i-1],a[-i-1]))

gcd_r.reverse()

ans = max(gcd_r[1],gcd_l[-2])
for i in range(1,n-1):
    gcd = fractions.gcd(gcd_l[i-1],gcd_r[i+1])
    ans = max(ans,gcd)

print(ans)
from numba import jit

N=int(input())
S=input()
R=0
G=0
B=0
for i in range(N):
    s=S[i]
    if s=="R":
        R+=1
    elif s=="G":
        G+=1
    else:
        B+=1
ans=R*G*B

@njit
def calc(ans):
    for i in range(N-2):
        for j in range(i+1, N-1):
            if 0<=j+j-i<N:
                si=S[i]
                sj=S[j]
                sk=S[2*j-i]
                if si!=sj and sj!=sk and sk!=si:
                    ans-=1
    return ans
print(calc(ans))


### FIXED CODE ###

N=int(input())
S=input()
count=0
R=0
G=0
B=0
for i in range(N):
  if S[i]=="R":
    R+=1
  if S[i]=="G":
    G+=1
  if S[i]=="B":
    B+=1
count=0
for i in range(N-2):
  for j in range(i,N-1):
    k=j+j-i
    try:
      if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
        count+=1
    except:
      pass
    
print(R*G*B-count)
while True:

    a = input()
    # if a == "0 0 0 0 0":
    #     break
    a = a.split(" ")
    b = []
    sum = 0
    for i in a:
        b.append(int(i))
        sum += int(i)
    if sum == 0:
        break
    c = input()
    c = c.split(" ")
    d = []
    for i in c:
        d.append(int(i))
    if b[4] == d[0]:
        print(0)
        continue
    ans = 0
    x = b[4]
    for i in d:
        for e in range(10001):
            x = (b[1] * x + b[2]) % b[3]
            print("x: " ,x)
            ans = ans + 1
            if x == i:
                break
    if ans >= 10001:
        ans = -1
    print(ans)

quit()


### FIXED CODE ###

a = int(input())
b = []
clo = True
for i in range(a):
    b.append(input())

c = int(input())
for i in range(c):
    d = input()
    for j in range(a):
        if d == b[j]:
            know = True
            break
        else:
            know = False
    if know:
        if clo:
            clo = False
            print("Opened by " + d)
        else:
            clo = True
            print("Closed by " + d)
    else:
        print("Unknown " + d)
s in sys.stdin:
    a,b,n=map(int,s.split())
    a=a%b
    s=0
    for i in range(n):
        a*=10
        s+=a/b
        a%=b
    print s

### FIXED CODE ###

import sys
for s in sys.stdin:
    a,b,n=map(int,s.split())
    s=0
    while n:
        a=a%b*10
        s+=a/b
        n-=1
    print s
while True:
  x, y = map(int, raw_input().split())
   if x>y:
    print y, x 
  elif x<y:
    print x, y
  continue
  elif x == 0 and y == 0:
    break
  elif x==y:
    print x, y
  continue
  

### FIXED CODE ###

while True:
  x, y = map(int, raw_input().split())
  if x == 0 and y == 0:
    break
  elif x > y:
    print y, x 
  elif x < y or x == y:
    print x, y
S = list(input())
invS = []
for s in reversed(S):
    invS.append(s)
cnt = 0
loop = 0
i,j = 0,0
while i+j != len(S)-1:
    if S[i] == invS[j]:
        i += 1
        j += 1
    elif S[i] == "x":
        cnt += 1
        i += 1
    elif invS[j] == "x":
        cnt += 1
        j += 1
    else:
        cnt = -1
        break
print(cnt)


### FIXED CODE ###

S = list(input())
invS = []
for s in reversed(S):
    invS.append(s)
cnt = 0
loop = 0
i,j = 0,0
while i+j < len(S)-1 and i <= len(S)-1 and j <= len(S)-1 :
    if S[i] == invS[j]:
        i += 1
        j += 1
    elif S[i] == "x":
        cnt += 1
        i += 1
    elif invS[j] == "x":
        cnt += 1
        j += 1
    else:
        cnt = -1
        break
print(cnt)
N, K = map(int, input().split())
A = list(map(int, input().split()))
teleport = dict()
for i, a in enumerate(A):
    teleport[i+1] = a

state = 1
connect = [1]
looplen= 10**18
for n in range(N):
    state = teleport[state] 
    #print(state)
    #print(connect)
    if state in connect:
        loop_init = connect.index(state)
        looplen = n-connect.index(state)+1
        break
    else:
        connect.append(state)
        
index = (k-loop_init)%looplen
end = connect[loop_init+index]
print(end)

### FIXED CODE ###

looplenn,k = map(int,input().split())
a = [0]+list(map(int,input().split()))

def bin(arr,val):
    left,right = 0,len(arr)-1
    while left<=right:
        mid = (left+right)//2
        if arr[mid]==val: return 1
        elif arr[mid]<val: left = mid + 1
        else: right = mid - 1
    return 0

know = []
now = 1
while not bin(know, now):
    know.append(now)
    now = a[now]

loop_start = a[know[-1]]
for i,num in enumerate(know):
    if num == loop_start:
        loop_init = i
        loop = know[i:]
        break

#print(know,start,loop)

cnt = len(loop)
if k < len(know):
    ans = know[k]
else:
    ans = loop[(k-loop_init)%cnt]
# ans = loop[k%cnt]


print(ans)
w,h,x,y = map(int,input().split())

if(2*x == w and 2*y ==h) :
    ff = 1
else :
    ff = 0

print(str(w * h / 2) + " " + str(ff))



### FIXED CODE ###

x,a = map(int,input().split())
if ( x < a ) :
    print(0)
else :
    print(10)
def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret

def eratosththenes(N):
    if N == 0:
        return [0]
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    for i in range(N+1):
        if work[i]:
            for j in range(2* i, N+1, i):
                work[j] = False
    return work


N = int( input())
A = [ int( input()) for _ in range(N+1)]
E = eratosththenes(N)
Primes = [ i for i in range(N+1) if E[i] == 1]
ANS = []
F = factors(A[0])
for f in F:
    if f >= N+1:
        Primes.append(f)
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1):
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*(p-1)
        for i in range(N+1):
            poly[(N-i)%(p-1)] = (poly[(N-i)%(p-1)] + A[i])%p
        check = 1
        if sum(poly) != 0 or A[N]%p != 0:
            check = 0
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)


### FIXED CODE ###

def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret

def eratosththenes(N):
    if N == 0:
        return [0]
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    for i in range(N+1):
        if work[i]:
            for j in range(2* i, N+1, i):
                work[j] = False
    return work


N = int( input())
A = [ int( input()) for _ in range(N+1)]
E = eratosththenes(N)
Primes = [ i for i in range(N+1) if E[i] == 1]
ANS = []
F = factors( abs(A[0]))
for f in F:
    if f >= N+1:
        Primes.append(f)
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1):
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*(p-1)
        for i in range(N+1):
            poly[(N-i)%(p-1)] = (poly[(N-i)%(p-1)] + A[i])%p
        check = 1
        if sum(poly) != 0 or A[N]%p != 0:
            check = 0
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)
n = int(input())
x = list(map(int,input().split()))
mod=1e9+7
a = [-1]*(n+1)
def step(i):
    if i>=n-1:
        a[i]=0
        return x[-1]
    if(a[i]!=-1):return x[i]
    a[i] = min(abs(step(i+1)-x[i])+a[i+1],abs(step(i+2)-x[i])+a[i+2])%mod;
    return x[i]
step(0)
print(a[0]%mod)


### FIXED CODE ###

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

dp = [0, abs(h[1]-h[0])]
if n >2:
    for i in range(2,n):
        dp.append(min(abs(h[i]-h[i-2])+dp[-2], abs(h[i]-h[i-1])+dp[-1]))
else:
    print(dp[-1])
    exit()

print(dp[-1])
from math import gcd

def resolve():
	n = int(input())
	ans = int(input())
	for i in range(n-1):
		v = int(input())
		ans = ans * v // gcd(ans, v)
	print(ans)


### FIXED CODE ###

def resolve():
	s = input()
	print('Yes' if s[0] == s[-1] else 'No')
resolve()
N, M = map(int, input().split())
p = []
S = []
for i in range(M):
    pp, SS = map(str, input().split())
    p.append(pp)
    S.append(SS)

a = []
for i in range(M):
    a.append(int(p[i]))

AC = 0
P = 0

Q = []
R = []
for i in range(N):
    Q.append(0)
    R.append(0)

for i in range(M):
    index = a[i] - 1
    if Q[index] == 0 and S[i] == 'AC':
        AC = AC + 1
        Q[index] = 1
    elif Q[index] == 0 and S[i] == 'WA':
        R[i - 1] = R[i - 1] + 1

for i in range(N):
    if Q[i] == 0:
        P = 0
    else: P = P + R[i]

print(AC, P)

### FIXED CODE ###

N, M = map(int, input().split())
p = []
S = []
for i in range(M):
    pp, SS = map(str, input().split())
    p.append(pp)
    S.append(SS)

a = []
for i in range(M):
    a.append(int(p[i]))

AC = 0
P = 0

Q = []
R = []
for i in range(N):
    Q.append(0)
    R.append(0)

for i in range(M):
    index = a[i] - 1
    if Q[index] == 0 and S[i] == 'AC':
        AC = AC + 1
        Q[index] = 1
    elif Q[index] == 0 and S[i] == 'WA':
        R[a[i] - 1] = R[a[i] - 1] + 1

for i in range(N):
    if Q[i] == 0:
        P = P
    else: P = P + R[i]

print(AC, P)
from collections import defaultdict

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

dict = defaultdict(int)

for i in range(M):
  B, C = map(int, input().split())
  dict[C] += B

idx = 0
for k, v in sorted(dict.items(), key=lambda x: -x[0]):
  for _ in range(v):
    if A[idx] < k and idx <= len(A):
      A[idx] = k
      idx += 1
    else:
      print(sum(A))
      exit()

print(sum(A))
  

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

from collections import defaultdict

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

dict = defaultdict(int)

for i in range(M):
  B, C = map(int, input().split())
  dict[C] += B

idx = 0
for k, v in sorted(dict.items(), key=lambda x: -x[0]):
  for _ in range(v):
    if idx+1 <= len(A):
      if A[idx] < k:
      	A[idx] = k
      	idx += 1
      else:
        print(sum(A))
        exit()
    else:
      print(sum(A))
      exit()
      
      
print(sum(A))
N=input()
A = [int(a) for a in input().split()]

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

mat = [1]
divs_set = set()
divs_powers = {}
for a in A:
    tmp = factorization(a)
    for div in tmp:
        if div[0] not in divs_set:
            divs_set.add(div[0])
            divs_powers[div[0]] = div[1]
        else:
            if divs_powers[div[0]] < div[1]:
                divs_powers[div[0]] = div[1]

Z = 1
for n in divs_set:
    Z = Z*(n**divs_powers[n])

B = [0]*N
for i, a in enumerate(A):
    B[i] = int(Z/a)%(10**9+7)

print(B)
print(int(sum(B))%(10**9+7))

### FIXED CODE ###

import math
from collections import defaultdict

n = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

divisor_primes = defaultdict(int)

def prime_factrizer(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

for a in A:
    factrized_a = prime_factrizer(a)
    for prime in factrized_a:
        divisor_primes[prime[0]] = max(divisor_primes[prime[0]],prime[1])

invs = [1] * (max(A) + 1)
for i in range(2, max(A) + 1):
    invs[i] = mod - invs[mod % i] * (mod//i) % mod

lcm = 1
for key in divisor_primes.keys():
    power = divisor_primes[key]
    div = 1
    for i in range(power):
        div *= key
        div %= mod
    lcm *= div

ans = 0

for a in A:
    ans += invs[a]
    ans %= mod
ans *= lcm
ans %= mod
print(ans)
import itertools as it
import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())


directions = np.array([[1, 0], [0, 1], [-1, 0], [0, -1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def serch(x, count):
    #print("top", x, count)

    for d in directions:
        nx = d+x
        # print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)

    return count


N, K = acinput()


ary = [acinput() for i in range(N)]
x = list(map(lambda x: x[0], sorted(ary, key=lambda s: s[0])))
y = list(map(lambda x: x[1], sorted(ary, key=lambda x: x[1])))


#print(list(it.combinations(y,2)))
#print(list(x))

res = 10**20
for sy in it.combinations(y, 2):
    #print(sy)
    for sx in it.combinations(x, 2):
        #print(sx)
        #print(sy, sx)
        count = 0
        for sa in ary:
            
            if sy[0] <= sa[1] and sa[1] <= sy[1]:
                if sx[0] <= sa[0] and sa[0] <= sx[1]:
                    count += 1

        #print(count)
        if count >= K:
            dx = np.diff(sx)[0]
            dy = np.diff(sy)[0]
            #print(dx,dy)
            res = min(res, dx*dy)
            #print(res)

print(res)



### FIXED CODE ###


import itertools as it

from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())



N, K = acinput()


ary = [acinput() for i in range(N)]
x = list(map(lambda x: x[0], sorted(ary, key=lambda s: s[0])))
y = list(map(lambda x: x[1], sorted(ary, key=lambda x: x[1])))


#print(list(it.combinations(y,2)))
#print(list(x))

res = 10**20
for sy in it.combinations(y, 2):
    #print(sy)
    for sx in it.combinations(x, 2):
        #print(sx)
        #print(sy, sx)
        count = 0
        for sa in ary:
            
            if sy[0] <= sa[1] and sa[1] <= sy[1]:
                if sx[0] <= sa[0] and sa[0] <= sx[1]:
                    count += 1

        #print(count)
        if count >= K:
            #dx = np.diff(sx)[0]
            #dy = np.diff(sy)[0]
            dx=sx[1]-sx[0]
            dy=sy[1]-sy[0]
            #print(dx,dy)
            res = min(res, dx*dy)
            #print(res)

print(res)
N,X=map(int,input().strip().split())
x=list(map(int,input().strip().split()))

x.sort()

d=[]
for n in range(1,N):
    d.append(x[n]-x[n-1])

def gcd(a,b):
    x=max(a,b)
    y=min(a,b)
    tmp=x%y
    if tmp==0:
        return y
    else:
        gcd(y,tmp)

if len(d)==0:
    print(abs(x[0]-X))
else:
    D=d[0]
    for i in range(1,len(d)):
        D=gcd(D,d[i])
    print(D)

### FIXED CODE ###

N,X=map(int,input().strip().split())
x=list(map(int,input().strip().split()))
x.append(X)
x.sort()
    
d=[]
for n in range(1,N+1):
    d.append(x[n]-x[n-1])
    
def gcd(a,b):
    x=max(a,b)
    y=min(a,b)
    tmp=x%y
    if tmp==0:
        return y
    else:
        return gcd(y,tmp)
    
if len(d)<=1:
    print(d[0])
else:
    D=d[0]
    for i in range(1,len(d)):
        D=gcd(D,d[i])
    print(D)
from collections import Counter

n = int(input())

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

total = 0

cnt = [0]*n
for i in range(n):
    cnt[a[i]] += 1
    
for i in cnt:
    total += (i*(i-1))//2

for i in range(n):
    ans = 0
    before = (cnt[a[i]]*(cnt[a[i]]-1))//2
    after = ((cnt[a[i]]-1)*(cnt[a[i]]-2))//2
    
    ans = total - before + after
    print(ans)

### FIXED CODE ###

import collections

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

a=collections.Counter(A)

total=0
for v in a.values():
    if v>1:
        c=(v*(v-1))//2
        total+=c

for i in A:
    ans=total-(a[i]*(a[i]-1))//2+((a[i]-1)*(a[i]-2))//2
    print(ans)
n,k = input().split()
s = list(input())
s[int(k)] = s[int(k)].lower()
print(''.join(s))

### FIXED CODE ###

n,k = input().split()
s = list(input())
s[int(k)-1] = s[int(k)-1].lower()
print(''.join(s))
S = input()

max_length = 0
for i in range(len(S)):
  if S[i] in "ACGT":
    if i == len(S) - 1:
      length = 1
    else:
      for j in range(i+1, len(S)):
        if S[j] in "ACGT":
          length = j - i + 1
        else:
          break

    if length > max_length:
      max_length = length

print(max_length)

### FIXED CODE ###

S = input()

max_length = 0
for i in range(len(S)):
  if S[i] in "ACGT":
    if i == len(S) - 1:
      length = 1
    else:
      for j in range(i+1, len(S)):
        if S[j] in "ACGT":
          length = j - i + 1
        else:
          length = j - i
          break

    if length > max_length:
      max_length = length

print(max_length)
n=int(input())
s=input()
ans=s

c=s.count('()')
while c!=0:
  s=list(s)

  i=0
  n_s=''
  while i<=len(s)-1:
    if s[i]=='(' and s[i+1]==')':
      i+=2
    else:
      n_s+=s[i]
      i+=1

  s=''.join(n_s)
  c=s.count('()')

c_a=s.count('(')
c_b=s.count(')')

ans='('*c_b+ans+')'*c_a
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=s
s+='#'

c=s.count('()')
while c!=0:
  s=list(s)

  i=0
  n_s=''
  while i<=len(s)-1:
    if s[i]=='(' and s[i+1]==')':
      i+=2
    else:
      n_s+=s[i]
      i+=1

  s=''.join(n_s)
  c=s.count('()')

c_a=s.count('(')
c_b=s.count(')')

ans='('*c_b+ans+')'*c_a
print(ans)
10 0def main():
    n, k = map(int, input().split())
    if k == 0:
        print(n ** 2)
        exit()
    cnt = 0
    for i in range(1, n+1):
        p, r = divmod(n, i)
        cnt += max(0, p * (i - k)) + max(0, r - k + 1)
    
    print(cnt)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    if k == 0:
        print(n ** 2)
        exit()
    cnt = 0
    for i in range(1, n+1):
        p, r = divmod(n, i)
        cnt += max(0, p * (i - k)) + max(0, r - k + 1)
    
    print(cnt)
if __name__=='__main__':
    main()
A=int(input())
B=int(input())
C=int(input())
X=int(input())
a=0
for i in range(A+1):
  for j in range(B+1):
    if 0<=X-500*i-100*j<=50*C:
      a+=1
print(a)

### FIXED CODE ###

X,A,B=[int(input()) for i in range(3)]
print((X-A)%B)
s=input()
ans=""
for i in s:
  if i=="0" or i=="1":
    ans+=i
  else:
    if len(ans)!=0:
      del ans[-1]
print(ans)


### FIXED CODE ###

s=input()
ans=""
for i in s:
  if i=="0" or i=="1":
    ans+=i
  else:
    if len(ans)!=0:
      ans=ans[:-1]

print(ans)