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

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

A.sort(reverse=True)
ans = 0
N -= 2
ans += A[0]
A.pop(0)

if N == 0:
    print(ans)
    exit()
elif N == 1:
    ans += A[0]
    print(ans)
    exit()
elif N >= 2:
    q = N // 2
    r = N % 2
    for i in range(1, q + 1):
        ans += 2 * A[0]
        A.pop(0)
    if r == 1:
        ans += A[0]
    print(ans)


### FIXED CODE ###

import heapq

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

heapq.heapify(A)

ans = 0
N -= 2
ans += heapq.heappop(A) * (-1)

if N == 0:
    print(ans)
    exit()
elif N == 1:
    ans += A[0]
    print(ans)
    exit()
elif N >= 2:
    q = N // 2
    r = N % 2
    for i in range(1, q + 1):
        ans += 2 * heapq.heappop(A) * (-1)
    if r == 1:
        ans += heapq.heappop(A) * (-1)
    print(ans)
### BUGGY CODE ###

from collections import defaultdict

def main():
    S = input()
    d = defaultdict(int)
    d[0] = 1
    for i in range(len(S)):
        rem = int(S[-(i+1):])%2019
        d[rem] += 1
    ans = sum([d[i]*(d[i]-1)//2 for i in range(2019)])
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict

def main():
    S = input()
    d = defaultdict(int)
    d[0] = 1

    num = 0
    for digit, c in enumerate(S[::-1]):
        num += int(c) * pow(10, digit, 2019)
        num %= 2019
        d[num] += 1
    ans = sum([d[i]*(d[i]-1)//2 for i in range(2019)])
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import copy
def warshall_floyd(dist):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j],
                              dist[i][k] + dist[k][j])
    return dist
 
n, m, l = map(int, input().split()) #N:頂点数　M:辺の数 L:容量
dist = [[float("inf") for i in range(n)] for j in range(n)]
dist2 = copy.deepcopy(dist) 
for i in range(n):
    dist[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
 
warshall_floyd(dist)
 
 
for i in range(n):
    for j in range(n):
        if dist[i][j] <= l:
            dist2[i][j] = 1
 
warshall_floyd(dist2)
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    ans = dist2[s-1][t-1]-1
    if dist2[s-1][t-1] == float("inf"):
        ans = -1
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M, L = map(int, input().split())
    dist = [[float('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
        dist[A][B] = C
        dist[B][A] = C

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    e = [[float('inf')] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if dist[i][j] <= L:
                e[i][j] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                e[i][j] = min(e[i][j], e[i][k] + e[k][j])


    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if e[s][t] == float('inf'):
            print(-1)
            continue
        ans = e[s][t]
        print(ans-1)


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

N = int(input())

S = [input() for i in range(N)]

result = {}

for s in S:
    if s in result.keys():
        result[s] += 1
    else:
        result[s] = 0
result_max = sorted([i for i in result.keys() if result[i] == max(result.values())])

for r in result_max:
    print(r)

### FIXED CODE ###

import collections


N = int(input())

S = [input() for i in range(N)]

count = collections.Counter(S)


mx = max(count.values())

result = [key for key, val in count.items() if val == mx]
print("\n".join(sorted(result)))
### BUGGY CODE ###

N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a
cost = sum(s_cost)
for k in range(1,N):
    for i in range(N):
        i_index = i-k
        if (i-k) == -1:
            i_index+=N
        s_cost[i] = min(s_cost[i], s_cost[i_index])
    cost = min(cost, k*x + sum(s_cost))

print(cost)

### FIXED CODE ###

N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a.copy()
cost = sum(s_cost)
for k in range(1,N):
    for i in range(N):
        if s_cost[i] > a[(i-k)%N] :
            s_cost[i] = a[(i-k)%N]
    if cost > k*x + sum(s_cost):
        cost = k*x + sum(s_cost)
    else:
        break

print(cost)
### BUGGY CODE ###

# ABC139
# D
# ModSum

n = int(input())
print(sum(i for i in range(n)))

### FIXED CODE ###

# ABC139
# D
# ModSum

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

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

for i in range(N):
  print(A.count(i+1))

### FIXED CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
L = [0]*(N+1)
for i in range(N-1):
  L[A[i]] += 1
for l in L[1:]:
  print(l)
### BUGGY CODE ###

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

for i in range(n):
  for j in range(n):
    if listA[j]==i+1:
      print("%d " % (j+1), end="")
      break




### FIXED CODE ###

n=int(input())
listA=list(map(int,input().split()))
b=[0]*n

for i in range(n):
  b[listA[i]-1]=i+1
for i in range(n):
  print(b[i], end=" ")
### BUGGY CODE ###

N = int(input())
S = list(input() for i in range(N))
set = set(S)
max = 0

for i in set:
    if S.count(i) > max:
        max = S.count(i)
        list = [i]
    elif S.count(i) == max:
        list.append(i)

list.sort()

for i in list:
    print(i)


### FIXED CODE ###

import collections

N = int(input())
S = list(input() for i in range(N))
dict = {}

for l in S:
        if l in dict:
            dict[l] += 1;
        else:
            dict[l] = 1;
            
max = max(dict.values())

max_k_list = [kv[0] for kv in dict.items() if kv[1] == max]

max_k_list.sort()

for i in max_k_list:
    print(i)
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Summarize count of factor within list -- START --
def summarize_list(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res
# Summarize count of factor within list --- END ---

def main():
  n,p=LI()
  s=S()

  ans=0
  if p==2:
    for i,x in enumerate(s):
      if int(x)%2==0:
        ans+=i+1

  elif p==5:
    for i,x in enumerate(s):
      if int(x)%5==0:
        ans+=i+1

  else:
    a=[]
    for i in range(n)[::-1]:
      _i=n-1-i
      b=(10**_i*int(s[i]))%p
      a.append(b)

    # print(a)
    for i in range(1,n)[::-1]:
      a[i-1]+=a[i]
      a[i-1]%=p
    # print(a)

    a=summarize_list(a)
    # print(a)

    for x,y in a:
      if x%p==0:
        ans+=y
      if y>1:
        ans+=(y*(y-1))//2

  return ans

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,p=LI()
  s=S()

  ans=0
  if p==2 or p==5:
    for i,x in enumerate(s):
      if int(x)%p==0:
        ans+=i+1
    return ans

  _s=list(s)
  _s.reverse()

  a=[]
  i=1
  for x in _s:
    b=(i*int(x))%p
    a.append(b)
    i*=10
    i%=p

  b=[0]*p
  b[a[0]%p]=1
  for i in range(n-1):
    a[i+1]+=a[i]
    a[i+1]%=p
    b[a[i+1]]+=1

  for i,x in enumerate(b):
    if i==0:
      ans+=x
    if x>1:
      ans+=x*(x-1)//2

  return ans

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

r, g, b, n = [int(i) for i in input().split()]
t1 = n // r + 1
t2 = n // g + 1
ans = 0
for i in range(t1):
    for j in range(t2):
        t = r * i + g * j
        if (n - t) >= 0 and (n - t) % b == 0: ans += 1
print(ans)


### FIXED CODE ###

r, g, b, n = [int(i) for i in input().split()]
t1 = n // r + 1
t2 = n // g + 1
ans = 0
for i in range(t1):
    for j in range(t2):
        t = r * i + g * j
        if (n - t) >= 0 and (n - t) % b == 0: ans += 1
print(ans)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
s = input()
index = []
for i in range(len(s)):
    if s[i:i+2] == "AC":
        index.append(i)
for i in range(q):
    l, r = na()
    ct = 0
    for a in index:
        if l-1 <= a <= r-1 and l-1 <= a+1 <= r-1:
            ct += 1
    print(ct)

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
s = input()
ct = [0] * n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        ct[i+1] = 1
for i in range(n-1):
    ct[i+1] += ct[i]
for i in range(q):
    l, r = na()
    l -= 1
    r -= 1
    print(ct[r] - ct[l])
### BUGGY CODE ###

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

c = 0
d = 0 #i

while d <= n-1:
    s = a.count(a[d])
    if a[d] > s:
        c += s
    else:
        c += s-a[d]
    d = d + s
    
print(c)

### FIXED CODE ###

import bisect
n=int(input())
a = list(map(int,input().split()))
a.sort()
 
c = 0
d = 0 #i
 
while d <= n-1:
    s2 = bisect.bisect_right(a,a[d])
    s = s2-d
    if a[d] > s:
        c += s
    else:
        c += s-a[d]
    d = d + s
    
print(c)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
count = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if L[k] < L[j] + L[i]:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
from bisect import bisect_left
ans = 0
for i in range(N):
  for j in range(i+1, N):
    sum = L[i]+L[j]
    count = bisect_left(L, sum)
    ans += max(0, count-j-1)
print(ans)
### BUGGY CODE ###

import bisect
n=int(input())
l=list(sorted(map(int,input().split())))
count=0
for i in range(1,n):
    for j in range(i+1,n):
        p=l[i]+l[j]
        count+=min(bisect.bisect_left(l,p),i)-min(bisect.bisect_left(l,l[j]-l[i]+1),i)
print(count)


### FIXED CODE ###

import bisect
n=int(input())
l=list(sorted(map(int,input().split())))
count=0
for i in range(1,n):
    for j in range(i+1,n):
        p=l[i]+l[j]
        count+=min(bisect.bisect_left(l,p),i)-min(bisect.bisect_left(l,l[j]-l[i]+1),i)
print(count)
### BUGGY CODE ###

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

mod = 10**9 + 7
dp = [[0] * (k+1) for _ in range(n+1)]

dp[0][0] = 1
for i in range(1, n+1):
    cum = [0] * (k+2)
    for j in range(k+1):
        cum[j+1] = (cum[j] + dp[i-1][j]) % mod
        dp[i][j] += cum[j+1] - cum[max(0, j-a[i-1])]
        dp[i][j] %= mod

print(dp[n][k])

### FIXED CODE ###

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

mod = 10**9 + 7
dp = [[0] * (k+1) for _ in range(n+1)]

dp[0][0] = 1
for i in range(1, n+1):
    cum = [0] * (k+2)
    for j in range(k+1):
        cum[j+1] = (cum[j] + dp[i-1][j]) % mod
        dp[i][j] += cum[j+1] - cum[max(0, j-a[i-1])]
        dp[i][j] %= mod

print(dp[n][k])
### BUGGY CODE ###

import numpy as np

size=input()
pro=input()

p=np.array(pro.split(" "),dtype=np.int32)
p=np.sort(p)

k_end=max(p)
k_start=min(p)

check=p[int(len(p)/2)]


c=0
for k in range(k_start,k_end+1):
    if(check+1<k):
        break
    a=len(p[k<=p])
    b=len(p[k>p])
    if(a==b):
        c+=1
    else:
        pass
print(c)

### FIXED CODE ###

import numpy as np

size=input()
pro=input()

p=np.array(pro.split(" "),dtype=np.int32)
p=np.sort(p)

me=int(len(p)/2)

print(p[me]-p[me-1])
### BUGGY CODE ###

import copy
N,M=map(int,input().split())

bridge=[0]*(N-1)
l=[]
for _ in range(M):
  l.append(list(map(int,input().split())))

for sl in l:
  for i in range(sl[0]-1,sl[1]-1):
    bridge[i]+=1
ans=0
# bridge=[4,6,6,4]
while max(bridge)>=1:
  m=bridge.index(max(bridge)) #m=1
  l1=copy.deepcopy(l)
  for sl in l1:
    if(m>=sl[0]-1 and m<sl[1]-1):
      for j in range(sl[0]-1,sl[1]-1):
        bridge[j]-=1
      l.remove(sl)
  ans+=1
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(M)]
l.sort(key= lambda x: x[1])
removed = 0
ans = 0
for i in l:
  s = i[1]
  if removed<i[0]:
    removed = s-1
    ans+=1

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


N=int(input())
li=[]
for i in range(N):
  li.append(input())
count=0
from collections import Counter
 
def verify_anagrams(w1, w2):
    f = lambda y: "".join(sorted(map(lambda x: x.replace(' ', '').lower(), y)))
    return f(w1) == f(w2)
for i in range(N):
  for j in range(i+1):
    if i != j:
      if verify_anagrams(li[i],li[j]):
        count+=1
print(count)

### FIXED CODE ###

N=int(input())
#li=[input() for i in range(N)]
count=0
dic={}
for i in range(N):
  s=input()
  sorted_s="".join(sorted(s))
  count += dic.get(sorted_s, 0)
  dic[sorted_s] = dic.get(sorted_s, 0) + 1
print(count)
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
ab = []
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
    ab.append((a, b))

colors = defaultdict(int)


k = 1
init_v = 0
for v in range(n):
    if k < len(edges[v]):
        k = len(edges[v])
        init_v = v

def dfs(v, parent):
    palette = [i for i in range(1, k+1) if i != colors[(v, parent)]]
    for v2 in edges[v]:
        if v2 == parent:
            continue
        color = palette.pop()
        colors[(v, v2)] = color
        colors[(v2, v)] = color
        dfs(v2, v)


dfs(init_v, -1)

print(k)
for a, b in ab:
    print(colors[(a, b)])


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
ab = []
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
    ab.append((a, b))

colors = defaultdict(int)


k = 1
init_v = 0
for v in range(n):
    if k < len(edges[v]):
        k = len(edges[v])
        init_v = v


def dfs(v, parent):
    palette = [i for i in range(len(edges[v])+1, 0, -1)
               if i != colors[(parent, v)]]
    for v2 in edges[v]:
        if v2 == parent:
            continue
        color = palette.pop()
        colors[(v2, v)] = color
        colors[(v, v2)] = color
        dfs(v2, v)


dfs(init_v, -1)

print(k)
for a, b in ab:
    print(colors[(a, b)])
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n=ni()
a=nl()
nums = [0]*10**6
for i in range(n):
  nums[a[i]]+=1
q=ni()
for i in range(q):
  b,c=nm()
  nums[c]+=nums[b]
  nums[b]=0
  ans=0
  for j in range(len(nums)):
    ans+=nums[j]*j

  print(ans)


### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n=ni()
a=nl()
nums = [0]*10**6
for i in range(n):
  nums[a[i]]+=1
q=ni()
ans=0
for i in range(len(nums)):
  ans+=nums[i]*i

for i in range(q):
  b,c=nm()
  ans-=nums[b]*b
  ans+=nums[b]*c
  nums[c]+=nums[b]
  nums[b]=0
  print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a=list(map(int,input().split()))
bc=[]
for _ in range(m):
  bc.append(list(map(int,input().split())))

for i in bc:
  a.sort()
  b,c=i[0],i[1]
  for j in range(i[0]):
    if a[j]<i[1]:
      a[j]=i[1]

print(sum(a))

### FIXED CODE ###

n,m = map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)

for b,c in bc:
  a.extend([c]*b)
  if len(a) > n*2:
    break

a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

N = int(input())
li = list(map(int, input().split()))
an = []
for i in range (1,N+1):
    an.append(li.index(i) + 1)
an=[str(a) for a in an]
an=" ".join(an)
print(an)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(0,n):
  b[a[i]-1]=i+1
ans=''
for i in range(n):
  ans+=str(b[i])+' '
print(ans)
### BUGGY CODE ###

from fractions import gcd
def init(init_val,n):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def segfunc(x,y):
    if x*y == 0:
        return max([x,y])
    return gcd(x,y)

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res
N = int(input())
a = list(map(int,input().split()))
#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg=[ide_ele]*2*num

init(a,N)
res = 0
for i,elem in enumerate(a):
    update(i,0)
    tmp = query(0,N)
    if tmp >= res:
        res = tmp
    update(i,a[i])
print(res)


### FIXED CODE ###

from fractions import gcd
def init(init_val,n):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def segfunc(x,y):
    return gcd(x,y)

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res
N = int(input())
a = list(map(int,input().split()))
#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg=[ide_ele]*2*num

init(a,N)
res = 0
for i in range(N):
    tmp = gcd(query(0,i),query(i+1,N))
    if tmp >= res:
        res = tmp
print(res)
### BUGGY CODE ###

n = int(input())

data  = input().split()

for m in range(n):
    data[m] = int(data[m])

res = []

for i in range(1,n+1):
    for m in range(len(data)):
        if i == data[m]:
            res.append(m+1)
res = map(str, res)

print(' '.join(res))

### FIXED CODE ###

n = int(input())

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

res = [0]*n

rest = ""

for i in range(0,n):
    res[(n-data[i])*-1-1] = i+1

res = map(str, res)

print(' '.join(res))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))

for _ in range(q):
    n, x, m = map(int, input().split())
    l = []
    for i in range(k):
        l.append(d[i]%m)
    zero = l.count(0)
    total = x%m
    zero_total = zero*((n-1)//k)
    s = n
    n -= 1
    n -= n//k * k
    t = sum(l[:n])
    total += sum(l)*((s-1)//k)
    total += t
    total //= m
    zero_total += l[:n].count(0)
    print(s-1-total-zero_total)


### FIXED CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))
query = [None]*q
for i in range(q):
    query[i] = list(map(int, input().split()))

def answer_query(n, x, m):
    l = [m if i%m == 0 else i%m for i in d]
    count = n // k
    rem = n % k
    s = sum(l)
    total = s%m * count + x%m
    for i in range(rem):
        total += l[i]

    total //= m
    total += s//m * count

    print(n-total)


for n, x, m in query:
    answer_query(n-1, x, m)
### BUGGY CODE ###

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

small = 0
while small < n and a[small] < k:
    small += 1
n = small


cnt = 0
for c in range(n):
    able = [False for i in range(k)]
    able[0] = True
    for i in range(n):
        if c==i:
            continue
        for j in range(k-a[i]-1, -1, -1):
            if able[j]:
                able[j+a[i]] = True
    if not any(able[k-a[c]:k]):
        cnt += 1

print(cnt)



### FIXED CODE ###

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

small = 0
while small < n and a[small] < k:
    small += 1
n = small


cnt = 0
able = [False for i in range(k)]
able[0] = True
min_need = n
max_able = 0
i = n-1
while i >= 0:
    if max_able + a[i] >= k:
        min_need = i
        for j in range(min_need):
            if max_able + a[j] >= k:
                min_need = i
                break
    for j in range(min(max_able, k-a[i]-1), -1, -1):
        if able[j]:
            able[j+a[i]] = True
            max_able = max(j+a[i], max_able)
    i -= 1
print(min_need)
### BUGGY CODE ###

import bisect
n = int(input())
a = list(map(int,input().split()))
a.sort()
 
b = [2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2,0]
 
c = [0]*n #使ったら1
 
res = 0
 
for i in range(31):
    k1 = bisect.bisect_left(a,b[i+1])
    k2 = bisect.bisect_right(a,b[i])
 
    if k2 > k1:
 
        for j in range(k1,k2):
            if c[j] == 0:
                w1 = bisect.bisect_left(a,b[i]-a[j])
                w2 = bisect.bisect_right(a,b[i]-a[j])
 
                if w2 >w1:
                    p = w1
                    while p != w2:
                        if c[p] == 0 and j != p:
                            res += 1
                            c[p] = 1
                            c[j] = 1
                            p = w2-1
                        p += 1
 
print(res)

### FIXED CODE ###

import bisect
 
N = int(input())
A = [int(a) for a in input().split()]
A = sorted(A)
 
c = 0
for i in range(N - 1 , -1, -1):
    if A[i] == int(A[i]):
        b = 1
        while b <= A[i]:
            b <<= 1
 
        j = bisect.bisect_left(A, b - A[i])
        if i > j:
            if b - A[i] == A[j]:
                c += 1
                A[j] = A[j] - 0.5
                A[i] = A[i] + 0.5
print(c)
### BUGGY CODE ###

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

if sum(a) % ( (1 + n) * n // 2 ) != 0:
    print('NO')
    exit()

while a[0] > 0:
    temp = min(a)
    if temp < 0:
        print('NO')
        exit()
    p = a.index(min(a))
    for i in range(n):
        a[(p + i) % n] -= i + 1

if min(a) < 0 or sum(a) != 0:
    print('NO')
else:
    print('YES')


### FIXED CODE ###

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

if n == 1:
    print('YES')
    exit()

if sum(a) % ( (1 + n) * n // 2 ) != 0:
    print('NO')
    exit()

k = sum(a) // ( (1 + n) * n // 2 )

temp = k - a[0] + a[n - 1]
if temp % n != 0 or temp < 0:
    print('NO')
    exit()

d = temp // n
for i in range(1, n):
    temp = k - a[i] + a[i - 1]
    if temp % n != 0 or temp < 0:
        print('NO')
        exit()
    d += temp // n

print('YES')