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

import copy

import math


def main():
    import collections

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

    for k in range(N):
        tmp_A = ignore(A, k)
        tmp_A = collections.Counter(tmp_A)
        su = 0
        for c in tmp_A:
            pair = tmp_A[c]
            if pair >= 2:
                su += combinations_count(pair, 2)
        print(su)


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def ignore(A, i):
    x = copy.deepcopy(A)
    del x[i]
    return x


if __name__ == '__main__':
    main()


### FIXED CODE ###



def main():
    import collections

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

    allc = collections.Counter(A)
    # all_list = [0]*N
    allsu = 0
    for pairs in sorted(allc.values(), reverse=True):
        allsu += pairs*(pairs-1)//2

    for a in A:
        num = allc[a]
        print(allsu - (num-1))

    # for i in range(N):
    #     x = A[i]
    #     A[i] = 0
    #     tmp_A = cc(A)
    #     su = 0
    #     for pairs in sorted(tmp_A.values(), reverse=True):
    #         if pairs >= 2:
    #             su += pairs*(pairs-1)//2
    #         else:
    #             break
    #     A[i] = x
    #     print(su)


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

n=int(input())
lis=list(map(int,input().split()))
ans=lis[0]
for i in range(1,n):
    ans*=lis[i]
if ans>1000000000000000000:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n=int(input())
lis=list(map(int,input().split()))
ans=1
for i in lis:
    ans*=i
    if ans>1000000000000000000:
        ans=-1
        break
if 0 in lis:
    ans=0

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

import itertools

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

def solve():
    # print(N, A)
    # print(Xs)

    count = 0
    for n in range(1, N + 1):
        # print(list(itertools.combinations(Xs, n)))
        combs = list(itertools.combinations(Xs, n))
        for comb in combs:
            if sum(comb) / len(comb) == A:
                count += 1

    return count

res = solve()
print(res)


### FIXED CODE ###

def solve():
    def recur(i, n, total):
        # print("i, n, total", i, n, total)

        if not TABLE[i][n][total] == -1:
            # print('cache!')
            return TABLE[i][n][total]

        if not i < N:
            if n > 0 and total == A * n:
                return 1
            return 0

        ans1 = recur(i + 1, n, total)
        ans2 = recur(i + 1, n + 1, total + XS[i])

        # print(ans1, ans2)

        TABLE[i][n][total] = ans1 + ans2
        return TABLE[i][n][total]

    N, A = tuple(map(int, input().split()))
    XS = tuple(map(int, input().split()))

    TABLE = []
    for _ in range(N + 1):
        lines = [[-1 for x in range(N * 50 + 1)] for y in range(N + 1)]
        TABLE.append(lines)

    return recur(0, 0, 0)


if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = []
    for _ in range(N):
        _a = list(map(lambda x: int(x)-1, input().split()))
        A.append(_a)
    ptrs = [0 for _ in range(N)]
    day = 0
    players = set([i for i in range(N)])
    finished = set()
    while True:
        todays_players = set()
        matched = False
        if len(finished) == N:
            break
        #print("------")
        for home in (players-finished):
            if home in finished:
                continue
            away = A[home][ptrs[home]]
            if away in finished:
                continue
            #print(home, away)
            away_opp = A[away][ptrs[away]]
            if home in todays_players or away in todays_players:
                continue
            if home == away_opp:
                ptrs[home] += 1
                ptrs[away] += 1
                todays_players.add(home)
                todays_players.add(away)
                matched = True
                if ptrs[home] == N-1:
                    finished.add(home)
                if ptrs[away] == N-1:
                    finished.add(away)
        #print(ptrs)
        if matched:
            day += 1
        else:
            day = -1
            break
    print(day)





if '__main__' == __name__:
    resolve()


### FIXED CODE ###

def resolve():
    N = int(input())
    A = []
    for _ in range(N):
        _a = list(map(lambda x: int(x)-1, input().split()))
        A.append(_a)
    ptrs = [0 for _ in range(N)]
    day = 0
    players = set([i for i in range(N)])
    finished = set()
    yest_players = set([i for i in range(N)])
    while True:
        todays_players = set()
        matched = False
        if len(finished) == N:
            break
        #print("------")
        for home in yest_players:
            if home in finished:
                continue
            away = A[home][ptrs[home]]
            if away in finished:
                continue
            #print(home, away)
            away_opp = A[away][ptrs[away]]
            if home in todays_players or away in todays_players:
                continue
            if home == away_opp:
                ptrs[home] += 1
                ptrs[away] += 1
                todays_players.add(home)
                todays_players.add(away)
                matched = True
                if ptrs[home] == N-1:
                    finished.add(home)
                if ptrs[away] == N-1:
                    finished.add(away)
        yest_players = todays_players
        #print(ptrs)
        if matched:
            day += 1
        else:
            day = -1
            break
    print(day)





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



import itertools
import math
from functools import reduce

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

K = int(input())
lis = list(itertools.product(range(1, K+1), repeat=3))

ans=0
for x, y, z in lis:
    ans += gcd(x, y, z)

print(ans)


### FIXED CODE ###



import itertools
import math
from functools import reduce

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

K = int(input())
lis = list(itertools.combinations_with_replacement(range(1, K+1), 3))

ans=0
for i, j, k in lis:
    if i==j and j==k and i==k:
        ans+=gcd(i, j, k)
    elif i!=j and j!=k and i!=k:
        ans+=6*gcd(i, j, k)
    else:
        ans+=3*gcd(i, j, k)

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

# -*- coding: utf-8 -*-
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]

dp = [K] * N


def calc_dp(n):
    return n - 1


for i in A:
    dp = list(map(calc_dp, dp))
    dp[i - 1] += 1


for j in dp:
    if j > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

# -*- coding: utf-8 -*-
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]

dp = [K] * N


def calc_dp(n):
    return n - Q


for i in A:
    # dp = list(map(calc_dp, dp))
    dp[i - 1] += 1

dp = list(map(calc_dp, dp))

for j in dp:
    if j > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

for i in A:
    if A.count(i)>1:
        print('NO')
        exit()
    
print('YES')

### FIXED CODE ###

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

if len(set(A))==len(A):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import numpy as np

N = int(input())

S = []
cnt = []
for i in range(N):
  s = input()
  if s in S:
    cnt[S.index(s)] += 1
  else:
    S.append(s)
    cnt.append(1)

cnt = np.array(cnt)
S = np.array(S)

ans = S[cnt==cnt.max()]
ans.sort()

for s in ans:
  print(s)

### FIXED CODE ###

N = int(input())

d = {}
for i in range(N):
  s = input()
  if s in d.keys():
    d[s] += 1
  else:
    d[s] = 1

M = max(d.values())
for j,k in sorted(d.items()):
  if k == M:
    print(j)
### BUGGY CODE ###

N,A,B = map(int,input().split())
if not (A+B-1 <= N <= A*B):
    print(-1)
    exit()
if B == 1:
    print(*list(range(1,A+1)))
    exit()

n = (N-A)//(B-1)
m = (N-A)%(B-1)

ans = list(range(1,A+1))
tmp = A+1
lds = 1
while tmp <= N:
    l = n if lds > m else n+1
    ans = list(range(tmp,tmp+l)) + ans
    tmp += l
    lds += 1
print(*ans)

### FIXED CODE ###

N,A,B = map(int,input().split())
if not (A+B-1 <= N <= A*B):
    print(-1)
    exit()
if B == 1:
    print(*list(range(1,A+1)))
    exit()

n = (N-A)//(B-1)
m = (N-A)%(B-1)

stack = [1,A+1]
lds_cnt = 1
while stack[-1] <= N:
    l = n if lds_cnt > m else n+1
    stack.append(stack[-1] + l)
    lds_cnt += 1

ans = []
while len(stack) > 1:
    ans += list(range(stack[-2], stack[-1]))
    stack.pop()
print(*ans)
### BUGGY CODE ###

N = int(input())

def crt(rs,ms):
    def _inv_gcd(a,b):
        if a==0: return (b,0)
        s,t,m0,m1 = b,a,0,1
        while t:
            u = s // t
            s -= t * u
            m0 -= m1 * u
            tmp = s
            s = t
            t = tmp
            tmp = m0
            m0 = m1
            m1 = tmp
        if m0 < 0: m0 += b//s
        return (s, m0)
    assert len(rs) == len(ms)
    n = len(rs)
    r0,m0 = 0,1
    for i in range(n):
        assert 1 <= ms[i]
        r1,m1 = rs[i] % ms[i], ms[i]
        if m0 < m1:
            r0,r1,m0,m1 = r1,r0,m1,m0
        if m0 % m1 == 0:
            if r0 % m1 != r1: return (0,0)
            continue
        g,im = _inv_gcd(m0,m1)
        u1 = m1 // g
        if (r1-r0) % g: return (0,0)
        x = (r1-r0) // g % u1 * im % u1
        r0 += x * m0
        m0 *= u1
        if r0 < 0: r0 += m0
    return (r0,m0)

divs = set()
m = 1
NN = 2*N
while m*m <= NN:
    if NN%m == 0:
        divs.add(m)
        divs.add(NN//m)
    m += 1

ans = NN-1
for x in divs:
    y = NN//x
    if y==1: continue
    r,m = crt([0,-1], [x,y])
    if r==m==0: continue
    ans = min(ans, r)

print(ans)

### FIXED CODE ###

N = int(input())

def crt(rs,ms):
    def _inv_gcd(a,b):
        if a==0: return (b,0)
        s,t,m0,m1 = b,a,0,1
        while t:
            u = s // t
            s -= t * u
            m0 -= m1 * u
            tmp = s
            s = t
            t = tmp
            tmp = m0
            m0 = m1
            m1 = tmp
        if m0 < 0: m0 += b//s
        return (s, m0)
    assert len(rs) == len(ms)
    n = len(rs)
    r0,m0 = 0,1
    for i in range(n):
        assert 1 <= ms[i]
        r1,m1 = rs[i] % ms[i], ms[i]
        if m0 < m1:
            r0,r1,m0,m1 = r1,r0,m1,m0
        if m0 % m1 == 0:
            if r0 % m1 != r1: return (0,0)
            continue
        g,im = _inv_gcd(m0,m1)
        u1 = m1 // g
        if (r1-r0) % g: return (0,0)
        x = (r1-r0) // g % u1 * im % u1
        r0 += x * m0
        m0 *= u1
        if r0 < 0: r0 += m0
    return (r0,m0)

divs = set()
m = 1
NN = 2*N
while m*m <= NN:
    if NN%m == 0:
        divs.add(m)
        divs.add(NN//m)
    m += 1

ans = NN-1
for x in divs:
    y = NN//x
    if y==1: continue
    r,m = crt([0,-1], [x,y])
    if r==m==0: continue
    ans = min(ans, r)

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

import sys
import collections
import numpy as np
e=sys.stdin.readlines()
N,M,Q=map(int,e[0].split())
dp=np.zeros([N+1,N+1])
for k,c in collections.Counter(e[1:M+1]).items():
    L,R=map(int,k.split())
    dp[1:L+1,R:N+1] += c
ans=''
for x in e[M+1:]:
    p,q=map(int,x.split())
    ans+=str(int(dp[p][q]))+'\n'
print(ans[:-1])

### FIXED CODE ###

import sys
def main():
    s = sys.stdin.readlines()
    N, M, Q = map(int, s[0].split())
    x = [[0] * N for _ in [0] * N]
    for e in s[1:M + 1]:
        L, R = map(int, e.split())
        x[L - 1][R - 1] += 1
    for k in range(1, N):
        for i in range(N - k):
            j = i + k
            x[i][j] += x[i][j - 1] + x[i + 1][j] - x[i + 1][j - 1]
    res = []
    for e in s[M + 1:]:
        p, q = map(int, e.split())
        res.append(x[p - 1][q - 1])
    print('\n'.join(map(str, res)))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n, m, q = map(int, input().split())
lr = tuple(tuple(map(int, input().split())) for _ in range(m))
pq = tuple(tuple(map(int, input().split())) for _ in range(q))

lr = sorted(lr, key=lambda x: x[1] - x[0])

for i in range(q):
    p, q = pq[i]
    c = 0
    for j in range(m):
        l, r = lr[j]
        if r - l > q - p:
            break
        if p <= l and r <= q:
            c += 1
    print(c)


### FIXED CODE ###

N, M, Q = map(int, input().split())

x = [[0 for j in range(N + 1)] for i in range(N + 1)]

for _ in range(M):
    L, R = map(int, input().split())
    x[N - L][R] += 1

for i in range(1, N + 1):
    for j in range(1, N + 1):
        x[i][j] += x[i][j - 1]

for j in range(1, N + 1):
    for i in range(1, N + 1):
        x[i][j] += x[i - 1][j]

for _ in range(Q):
    p, q = map(int, input().split())
    print(x[N - p][q])
### BUGGY CODE ###

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

list_ = []
for i in range(1, N):
  print(A.count(i))
print(0)

### FIXED CODE ###

import numpy as np

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

A.append(0)

for i in range(0, N-1):
  ans[A[i]] += 1
for i in range(1, N):
  print(ans[i])
print(0)
### BUGGY CODE ###

h,w,m=map(int,input().split())
s=[0]*m
t=[0]*m
temp=[0]*m
for i in range(m):
  sm,tm=map(int,input().split())
  s[i]=sm
  t[i]=tm
  temp[i]=[s[i],t[i]]
st=[0]*h
tt=[0]*w
for i in range(m):
  st[s[i]-1]=st[s[i]-1]+1
  tt[t[i]-1]=tt[t[i]-1]+1
smax=max(st)
tmax=max(tt)
ans=smax+tmax
maxs=[]
maxt=[]
for i in range(h):
  if st[i]==smax:
    maxs.append(i)
for i in range(w):
  if tt[i]==tmax:
    maxt.append(i)
c=0
for i in range(len(maxs)):
  for j in range(len(maxt)):
    if ([maxs[i]+1,maxt[j]+1]) not in temp:
      print(ans)
      exit()
else:
  print(ans-1)

### FIXED CODE ###

h,w,m=map(int,input().split())
s=[0]*m
t=[0]*m
temp=set()
for i in range(m):
  sm,tm=map(int,input().split())
  s[i]=sm
  t[i]=tm
  temp.add((s[i],t[i]))
st=[0]*h
tt=[0]*w
for i in range(m):
  st[s[i]-1]=st[s[i]-1]+1
  tt[t[i]-1]=tt[t[i]-1]+1
smax=max(st)
tmax=max(tt)
ans=smax+tmax
maxs=[]
maxt=[]
for i in range(h):
  if st[i]==smax:
    maxs.append(i)
for i in range(w):
  if tt[i]==tmax:
    maxt.append(i)

if len(maxs)*len(maxt)>m:
  print(ans)
else:
  for i in range(len(maxs)):
    for j in range(len(maxt)):
      if (maxs[i]+1,maxt[j]+1) not in temp:
        print(ans)
        exit()
  else:
    print(ans-1)
### BUGGY CODE ###

import queue
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        q = queue.Queue()
        q.put((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        while not q.empty():
            p = q.get()
            for dx, dy in zip(dxs, dys):
                if S[p[1]][p[0]] == '#':
                    continue
                field[p[1]][p[0]] = p[2]
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                q.put((x, y, p[2] + 1))
        cand.append(max([max(row) for row in field]))
print(max(cand))

### FIXED CODE ###

import queue
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            continue
        q = queue.Queue()
        q.put((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        field[j][i] = 0
        while not q.empty():
            p = q.get()
            for dx, dy in zip(dxs, dys):
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                field[y][x] = p[2] + 1
                q.put((x, y, p[2] + 1))
        cand.append(max(max(row) for row in field))
print(max(cand))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
import bisect
import math


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

XH = []
for _ in range(n):
    x, h = map(int, input().split())
    XH.append((x, h))
XH.sort()

X, H = [], []
for x, h in XH:
    X.append(x)
    H.append(h)
H = np.array(H)

answer = 0
for i in range(n):
    if H[i] <= 0:
        continue
    j = bisect.bisect(X, X[i] + 2 * d)
    bomb = math.ceil(H[i] / a)
    H[i:j] -= a * bomb
    answer += bomb

print(answer)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
import math


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

XH = []
for _ in range(n):
    x, h = map(int, input().split())
    XH.append((x, h))
XH.sort()

answer = 0
damage = 0
QUEUE = deque()
for x, h in XH:
    if QUEUE:
        while x > QUEUE[0][0]:
            damage -= QUEUE[0][1]
            QUEUE.popleft()
            if not QUEUE:
                break
    h -= damage
    if h <= 0:
        continue
    bomb = math.ceil(h / a)
    QUEUE.append((x + 2 * d, a * bomb))
    damage += a * bomb
    answer += bomb

print(answer)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
import fractions
from functools import reduce

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

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

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

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

v=lcm(*c)
ans=0

for i in range(n):
    ans+=v//c[i]

print(ans%mod)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
import fractions
from functools import reduce

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

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

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

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

v=lcm(*c)%mod
ans=0

for i in range(n):
    ans += v * pow(c[i],mod-2,mod)
    ans%=mod

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

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

### FIXED CODE ###

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

X, N = map(int, input().split())
i = list(map(int, input().split()))
if X not in i:
    print(X)
else:
    n = 1
    while n <=N+1:
        if X - n not in i:
            print(X - n)
            break
        else:
            if X+n not in i:
                print(X+n)
                break

### FIXED CODE ###

X, N = map(int, input().split())
i = list(map(int, input().split()))
if X not in i:
    print(X)
else:
    n = 1
    while n <=N+1:
        if X - n not in i:
            print(X - n)
            break
        else:
            if X+n not in i:
                print(X+n)
                break
        n +=1
### BUGGY CODE ###

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

ans = 0
pre_a = 0
i = 1
for a in A:
    if pre_a > a:
        ans += pre_a - a
    else:
        ans += 0
    pre_a = max(A[: i])
    i += 1

print(ans)


### FIXED CODE ###

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

ans = 0
max_a = 0
for a in A:
    if max_a < a:
        max_a = a
    else:
        ans += max_a - a

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

def solve():
    N = int(input())
    S = list(input())
    Q = int(input())
    set_dic = {}

    for i, s in enumerate(S):
        if s not in set_dic.keys():
            set_dic[s] = {i+1}
        else:
            set_dic[s].add(i+1)

    anslist = []

    for _ in range(Q):
        query1, query2, query3 = input().split()
        if query1 == "1":
            i = int(query2)
            c = query3
            for l in set_dic.values():
                l.discard(i)
            if c not in set_dic.keys():
                set_dic[c] = {i}
            else:
                set_dic[c].add(i)
        else:
            l = int(query2)
            r = int(query3)
            ansset = set()
            ans = 0
            for eachset in set_dic.values():
                for i in range(l, r + 1):
                    if i in eachset:
                        ans += 1
                        break
            anslist.append(ans)

    for i in anslist:
        print(i)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    S = list(input())
    Q = int(input())
    set_dic = {}

    for i, s in enumerate(S):
        if s not in set_dic:
            set_dic[s] = [i+1]
        else:
            bisect.insort_left(set_dic[s], i+1)

    anslist = []

    for _ in range(Q):
        query1, query2, query3 = input().split()
        if query1 == "1":
            i = int(query2)
            c = query3
            cap = S[i-1]
            if cap == c:
                continue
            set_dic[cap].remove(i)
            if c not in set_dic:
                set_dic[c] = [i]
            else:
                bisect.insort_left(set_dic[c], i)
            S[i-1] = c
        else:
            l = int(query2)
            r = int(query3)
            ansset = set()
            ans = 0
            for eachlist in set_dic.values():
                li = bisect.bisect_left(eachlist, l)
                ri = bisect.bisect_right(eachlist, r)
                if li != ri:
                    ans += 1
            anslist.append(ans)

    for i in anslist:
        print(i)

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

X = int(input())
A = int(pow(X, 0.2))
while True:
    diff = X - A**5
    if diff < 0:
        minus_flg = False
        diff = abs(diff)
    else:
        minus_flg = True
    B = pow(diff, 0.2)
    if (isinstance(B, float)) and B.is_integer():
        break
        A += 1
if minus_flg:
    B = int(B)*-1
print(A, int(B))


### FIXED CODE ###

X = int(input())

for a in range(-118, 121):
    for b in range(-118, 121):
        if (a**5 - b**5) == X:
            break
    else:
        continue
    break
print(a, b)
### BUGGY CODE ###

import copy
[n,x]=list(map(int,input().split()))
a=list(map(int,input().split()))
a0=copy.copy(a)
ans=0
for i in range(n-1):
	while a[i]+a[i+1]>x:
		a[i+1]-=1
for i in range(n):
	ans+=a0[i]-a[i]
print(ans)

### FIXED CODE ###

import copy
[n,x]=list(map(int,input().split()))
a=list(map(int,input().split()))
a0=copy.copy(a)
ans=0
if a[0]+a[1]>x and a[0]>x:
	ans+=a[0]-x
	a[0]-=a[0]-x
	if a[0]+a[1]>x:
		ans+=a[1]
		a[1]=0	
for i in range(n-1):
	if a[i]+a[i+1]>x:
		ans+=a[i]+a[i+1]-x
		a[i+1]-=a[i]+a[i+1]-x
		
print(ans)
### BUGGY CODE ###

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

ball = [0,0]
#左が青, 右が赤
while True:
    ball[0] += a
    if sum(ball) == n:
        print(ball[0])
        exit()
    elif sum(ball) > n:
        ball[0] -= sum(ball) - n
        print(ball[0])
        exit()
    
    ball[1] += b
    if sum(ball) >= n:
        print(ball[0])
        exit()

### FIXED CODE ###

n,a,b = map(int, input().split())
block = n // (a+b)
rest = n % (a+b)

ans = block*a + min(a,rest)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
for i in range(m):
    b,c=map(int,input().split())
    for i in range(b):
        if a[0]>=c:
            break
        a[0]=c
        a.sort()
print(sum(a))




### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
l=[]
for i in range(n):
    l.append([1,a[i]])
for i in range(m):
    l.append(list(map(int,input().split())))
l.sort(key=lambda x:x[1], reverse=True)
c=0
ans=0
for i in range(n+m):
    ans+=l[i][1]*l[i][0]
    c+=l[i][0]
    if c>n:
        ans-=l[i][1]*(c-n)
        break
print(ans)