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

h, n = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

dp = [(-(-i // a[0]) * b[0]) for i in range(h + 1)]
for i in range(1, n):
    for j in range(1, h + 1):
        dp[j] = min(dp[j], dp[max(j-a[i],0)] + b[i])

print(dp[-1])

### FIXED CODE ###

h, n = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

dp = [(-(-i // a[0]) * b[0]) for i in range(h + 1)]
for i in range(1, n):
    for j in range(1, h + 1):
        dp[j] = min(dp[j], dp[max(j-a[i],0)] + b[i])

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

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

a_2 = [0 for i in range(max(a))]
for i in range(max(a)):
    a_2[i] += a.count(i+1)

al = []
for i in a_2:
    al.append(int(i * (i-1) / 2))

for i in range(n):
    f = a[i]
    t = a_2[f-1] - 1
    print(int(sum(al)-(al[f-1]-t*(t-1)/2)))
    


### FIXED CODE ###

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

a_2 = [0 for i in range(n)]
for i in range(n):
    a_2[a[i]-1] += 1

al = [0 for i in range(n)]
c = 0
for i in a_2:
    if i > 1:
        al[c] += i * (i-1) / 2
    c += 1

sine = sum(al)
for i in range(n):
    f = a[i]
    t = a_2[f-1] - 1
    print(int(sine-(al[f-1]-t*(t-1)/2)))
### BUGGY CODE ###

N = int(input())
A = list(map(int, 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[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if arr == []:
        arr[n] = 1

    return arr

ans = 0
for a in A:
    arr = factorization(a)
    if 2 in arr:
        ans += arr[2]
print(ans)

### FIXED CODE ###

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

def factorization(n):
    arr = {}
    temp = n
    i = 2
    if temp % i == 0:
        cnt = 0
        while temp % i == 0:
            cnt += 1
            temp //= i
        arr[i] = cnt

    return arr

ans = 0
for a in A:
    arr = factorization(a)
    if 2 in arr:
        ans += arr[2]
print(ans)
### BUGGY CODE ###

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

cnt = 0

if k >= a:
    k = k - a #3
    cnt = cnt + 1*a  #1

    if k >= b:
        k = k - b #1

        if k >= c:
            cnt = cnt + -1*c
            k = k - c

        else:
            for i in range(0, k):
                cnt += -1
                k -= 1
    
    else:
        for i in range(0, k):
            k -= 1

else:
    for i in range(0, k):
        cnt += 1
        k -= 1
print(cnt)

### FIXED CODE ###

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

cnt = 0

if k >= a:
    k = k - a #3
    cnt = cnt + 1*a  #1

    if k >= b:
        k = k - b #1

        if k >= c:
            cnt = cnt + -1*c
            k = k - c

        else:
            cnt = cnt + -1*k
            k = k - k
    
    else:
        k = k - k

else:
    cnt = cnt + 1*k
    k = k - k
    
print(cnt)
### BUGGY CODE ###

from collections import deque
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[[]for i in range(a)]
for i in range(a-1):
  ca=c[i][0]
  cb=c[i][1]
  d[ca-1].append(cb-1)
  d[cb-1].append(ca-1)
g=[0 for i in range(a)]
q=deque()
q.append(0)
e=b
while len(q):
  i=q.pop()
  f=1
  h=len(d[i])
  g[i]=1
  if i==0:
    for j in range(h):
      f=f*(b-1-j)
  else:
    if h>0:
      for j in range(h-1):
        f=f*(b-2-j)
  e=(e*f)%1000000007
  g[i]=1
  for j in range(h):
    if g[d[i][j]]==0:
      q.append(d[i][j])


print(e%1000000007)
  

### FIXED CODE ###

from collections import deque
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]
d=[[]for i in range(a)]
for i in range(a-1):
  ca=c[i][0]
  cb=c[i][1]
  d[ca-1].append(cb-1)
  d[cb-1].append(ca-1)
g=[0 for i in range(a)]
q=deque()
q.append(0)
e=b
while len(q):
  i=q.pop()
  h=len(d[i])
  g[i]=1
  if i==0:
      f=b-1
  else:
    f=b-2
  g[i]=1
  for j in range(h):
    if g[d[i][j]]==0:
      q.append(d[i][j])
      e=(e*f)%1000000007
      f-=1


print(e%1000000007)
### BUGGY CODE ###

def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    l = list(map(int, input().rstrip('\n').split()))
    l.sort()
    cnt = 0
    d = collections.defaultdict(int)
    for i in range(n-2):
        for j in range(i+1, n-1):
            for k in range(j+1, n):
                if l[i] + l[j] > l[k]:
                    if (i, j, k) not in d:
                        cnt += 1
                        d[i, j, k]
                else:
                    break
    print(cnt)


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    import collections
    import bisect
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    l = list(map(int, input().rstrip('\n').split()))
    l.sort()
    cnt = 0
    d = collections.defaultdict(int)
    for i in range(n-2):
        for j in range(i+1, n-1):
            ma = l[i] + l[j]
            p = bisect.bisect_left(l, ma)
            if j < p:
                cnt += p - j - 1
    print(cnt)


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

from bisect import bisect_right
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]
S.append(10**11)
T = [int(input()) for _ in range(B)]
T.append(10**11)
Ds = {i:0 for i in range(A)}
Ds[A] = 10**11
cur = 0
for i in range(A):
    if S[i]<T[cur]:
        if cur==0:
            Ds[i] = T[cur]-S[i]
        else:
            Ds[i] = min(T[cur]-S[i],S[i]-T[cur-1])
    else:
        if T[cur+1]>S[i]:
                Ds[i] = min(T[cur+1]-S[i],S[i]-T[cur])
        else:
            ind = bisect_right(T,S[i])
            cur = ind-1
            Ds[i] = min(T[cur+1]-S[i],S[i]-T[cur])
Dt = {j:0 for j in range(B)}
Dt[B] = 10**11
cur = 0
for j in range(B):
    if T[j]<S[cur]:
        if cur==0:
            Dt[j] = S[cur]-T[j]
        else:
            Dt[j] = min(S[cur]-T[j],T[j]-S[cur-1])
    else:
        if S[cur+1]>T[j]:
            Dt[j] = min(S[cur+1]-T[j],T[j]-S[cur])
        else:
            ind = bisect_right(S,T[j])
            cur = ind-1
            Dt[j] = min(S[cur+1]-T[j],T[j]-S[cur])
for _ in range(Q):
    x = int(input())
    inds = bisect_right(S,x)
    if inds==0:
        cnts = S[0]-x+Ds[0]
    else:
        cnts = min(S[inds]-x+Ds[inds],x-S[inds-1]+Ds[inds-1])
    indt = bisect_right(T,x)
    if indt==0:
        cntt = T[0]-x+Dt[0]
    else:
        cntt = min(T[indt]-x+Dt[indt],x-T[indt-1]+Dt[indt-1])
    print(min(cnts,cntt))

### FIXED CODE ###

from bisect import bisect_right
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]
S.append(10**11)
S.insert(0,-10**11)
T = [int(input()) for _ in range(B)]
T.append(10**11)
T.insert(0,-10**11)
Ds = {i:0 for i in range(1,A+1)}
Ds[A+1] = 10**11
Ds[0] = 10**11
for i in range(1,A+1):
    ind = bisect_right(T,S[i])
    Ds[i] = min(T[ind]-S[i],S[i]-T[ind-1])
Dt = {j:0 for j in range(1,B+1)}
Dt[B+1] = 10**11
Dt[0] = 10**11
for j in range(1,B+1):
    ind = bisect_right(S,T[j])
    Dt[j] = min(S[ind]-T[j],T[j]-S[ind-1])
for _ in range(Q):
    x = int(input())
    inds = bisect_right(S,x)
    cnts = min(S[inds]-x+Ds[inds],x-S[inds-1]+Ds[inds-1])
    indt = bisect_right(T,x)
    cntt = min(T[indt]-x+Dt[indt],x-T[indt-1]+Dt[indt-1])
    print(min(cnts,cntt))
### BUGGY CODE ###

def main():
    n = int(input())
    x = []
    xl = {}
    maxtmp = 0
    for i in range(n):
        xx, ll = map(int,input().split())
        if maxtmp < xx:
            maxtmp = xx
        xl[xx] = ll
        x.append(xx)
    
    temp = [[] for i in range(maxtmp+2)]
    for i in range(maxtmp+1):
        if i in xl.keys():
            for j in range(i-xl[i]+1, i+xl[i]):
                if j < 0 or j > maxtmp+1:
                    continue
                temp[j].append(i)


    for i,a in enumerate(temp):
        if len(a) <= 1:
            continue
        else:
            for j in range(1,len(a)):
                if a[j] in x:
                    v = x.index(a[j])
                    x.pop(v)
    print(len(x))

if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    x = []
    xl = {}
    tmp = []
    ans = 0
    maxtmp = 0
    for i in range(n):
        xx, ll = map(int,input().split())
        if maxtmp < xx:
            maxtmp = xx
        low = xx-ll
        high = xx+ll
        lmh = [high,xx,low]
        tmp.append(lmh)


    tmp.sort()
    high = tmp[0][0]
    ans = 1
    for i in range(1,len(tmp)):
        a = tmp[i]
        if a[2] >= high:
            high = a[0]
            ans += 1
        else:
            continue

    print(ans)
    return


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

import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():

    S = input()
    S = S[::-1]
    MOD = 10 ** 9 + 7

    dp = [0] * 13
    dp[0] = 1

    mul = 1
    for i in range(len(S)):
        next_dp = [0] * 13
        if S[i] == '?':
            for k in range(10):
                for j in range(13):
                    jj = ((k * mul) + j) % 13
                    next_dp[jj] += dp[j]
                    next_dp[jj] %= MOD
        else:
            num = int(S[i])
            for j in range(13):
                jj = ((num * mul) + j) % 13
                next_dp[jj] += dp[j]
                next_dp[jj] %= MOD

        mul = mul * 10 % 13
        dp = next_dp

    print(dp[5])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

mod = 10 ** 9 + 7

S = input()
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= mod
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= mod
    mul = mul * 10 % 13

print(dp[len(S)][5])
### BUGGY CODE ###

import numpy as np

n,m=map(int,input().split())
c=[]
for i in range(m):
    c.append(int(input()))

d=[0]*(n+1)
d[0]=1
d[1]=1 if 1 not in c else 0
for j in range(2,n+1):
    if j in c:
        pass
    else:
        d[j]=(d[j-1]+d[j-2])%1000000007

print(d[n])

### FIXED CODE ###

import sys

n,m=map(int,input().split())
c=set(map(int,sys.stdin))

d=[0]*(n+1)
d[0]=1
d[1]=1 if 1 not in c else 0
for j in range(2,n+1):
    if j in c:
        pass
    else:
        d[j]=(d[j-1]+d[j-2])%1000000007

print(d[n])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += (A[i] ^ A[j])
        ans %= mod
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
cnt = [[0,0] for i in range(61)]
for i in range(61):
    for j in range(N):
        if ((A[j] >> i) & 1):
            cnt[i][1] += 1
        else:
            cnt[i][0] += 1

ans = 0
for i in range(61):
    ans += (cnt[i][0] * cnt[i][1]) * (2**i)
    ans %= mod
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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

s=input()
def roopR(l,n):
  for p in range(a):
    if list[l]==-1:
      if n%2==0:
        return l
      else:
        return l-1
    else:
      l += 1
      n += 1

def roopL(m,o):
  for q in range(a):
    if list[m]==1:
      if o%2==0:
        return m
      else:
        return m+1
    else:
      m -= 1
      o += 1

a=len(s)
endlist=[]
list=[]
for i in range(a):
  if s[i]=='R':
    list.append(1)
  else:
    list.append(-1)
for j in range(a):
  endlist.append(0)
for k in range(a):
  if list[k]==1:
    b=roopR(k,0)
    endlist[b] += 1
  else:
    b=roopL(k,0)
    endlist[b] += 1
print(*endlist)

### FIXED CODE ###

S=input()
dp=[0]*len(S)
a=0
for i in range(len(S)):
  if S[i]=='R':
    a+=1
  else:
    dp[i]+=a//2
    dp[i-1]+=a-a//2
    a=0
for i in range(len(S)-1,-1,-1):
  if S[i]=='L':
    a+=1
  else:
    dp[i]+=a//2
    dp[i+1]+=a-a//2
    a=0
print(*dp)
### BUGGY CODE ###


n = int(input())

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


import sys
if n == 2:
    print(max(a))
    sys.exit()


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)


def gcd_list(li):
    g = gcd(li[0], li[1])
    for i in range(2, n):
        g = gcd(g, a[i])
    return g


def max_gcd(a):
    g = gcd_list(a)
    a = [a[i]//g for i in range(n)]
    
    m = 1
    for i in range(n):
        b = a[:]
        del b[i]
        gg = gcd_list(b)
        m = max(m, gg)
    
    print(g * m)
    

max_gcd(a)

### FIXED CODE ###


n = int(input())

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


from functools import lru_cache
import sys
if n == 2:
    print(max(a))
    sys.exit()


@lru_cache(maxsize=100000)
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def gcd_list(li):
    if len(li) == 1:
        return li[0]
    g = gcd(li[0], li[1])
    for i in range(2, len(li)):
        g = gcd(g, li[i])
    return g


def gcd_list_2(li):
    g = gcd(li[0], li[1])
    if g == 1:
        return max(gcd_list([li[0]] + li[2:]), gcd_list(li[1:]))
    for i in range(2, n):
        if gcd(g, li[i]) == 1:
            if i == n - 1:
                return gcd_list(li[:i])
            gg = gcd_list(li[i+1:])
            bb = [gcd(li[x], gg) for x in range(i+1)]
            bb.sort()
            return bb[1]
        else:
            g = gcd(g, li[i])
    return g


def max_gcd(a):
    g = gcd_list(a)
    a = [a[i]//g for i in range(n)]
    m = gcd_list_2(a)
    print(g * m)


max_gcd(a)
### BUGGY CODE ###

n=int(input())
l=sorted(list(map(int,input().split())))
bitlist=[]
num=l[-1]
b1=[]
while num!=0:
  b1.append(num%2)
  num//=2
bitlist.append(b1)
for i in range(2,n+1):
  num=l[-i]
  b1=[]
  while num!=0 or len(b1)<len(bitlist[0]):
    b1.append(num%2)
    num//=2
  bitlist.append(b1)
d={}
for i in range(len(bitlist[0])):
  d[i]=0
  for j in range(n):
    d[i]+=bitlist[j][i]
ans=0
for i in d:
  ans=(ans+(2**i)*(n-d[i])*d[i])%(10**9+7)
print(ans)

### FIXED CODE ###

n=int(input())
l=sorted(list(map(int,input().split())))
num=l[-1]
b1=[]

while num!=0:
  b1.append(num%2)
  num//=2
d={}
for i in range(len(b1)):
  d[i]=b1[i]

for i in range(2,n+1):
  num=l[-i]
  count=0
  while num!=0 or count<len(b1):
    d[count]+=num%2
    num//=2
    count+=1

ans=0
table=[1]
for i in range(60):
  table.append((2*table[-1])%(10**9+7))
for i in d: 
  ans=(ans+table[i]*(n-d[i])*d[i])%(10**9+7)
print(ans)
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
path = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)
visited = [-1] * n
ans = [-1] * n
queue = deque([0])
while queue:
    pos = queue.popleft()
    visited[pos] = 1
    if len(path[pos]) > 0:
        l = path[pos]
        for i in range(len(l)):
            if visited[l[i]] == -1:
                if ans[l[i]] == -1:
                    ans[l[i]] = pos + 1
                queue.append(l[i])
print("Yes")
for i in range(1, n):
    print(ans[i])

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
path = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)
visited = [-1] * n
ans = [-1] * n
queue = deque([0])
while queue:
    pos = queue.popleft()
    visited[pos] = 1
    ll = path[pos]
    for l in ll:
        if visited[l] == -1:
            if ans[l] == -1:
                ans[l] = pos + 1
                queue.append(l)
print("Yes")
for i in range(1, n):
    print(ans[i])
### BUGGY CODE ###

S = list(input())
MOD = 10 ** 9 + 7

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

for i, s in enumerate(S):
    if s == '?':
        s = -1
    else:
        s = int(s)

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
    for l in range(13):
        dp[i + 1][l] %= MOD

print(dp[len(S)][5])


### FIXED CODE ###

S = list(input())
MOD = 10 ** 9 + 7

length = len(S)
dp = [[0] * 13 for _ in range(length + 1)]
dp[0][0] = 1

for i in range(length):
    if S[i] == '?':
        s = -1
    else:
        s = int(S[i])

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            index = (k * 10 + j) % 13
            dp[i + 1][index] = (dp[i + 1][index] + dp[i][k]) % MOD

print(dp[length][5])
### BUGGY CODE ###

n = int(input())
a = input()

max_c = 100000000

for i in range(0,n):
    l_count = 0
    r_count = 0
    for j in range(0, i):
        if a[j] == 'W':
            l_count += 1
    for j in range(i, n):
        if a[j] == 'E':
            r_count += 1
    if max_c > l_count + r_count:
        max_c = l_count + r_count

print(max_c)



### FIXED CODE ###

n = int(input())
a = input()

w_count = [0]
e_count = [0]

a_r = list(reversed(a))

for i in range(1, n+1):
    if a[i-1] == 'W':
        w_count.append(w_count[i-1] + 1)
    else:
        w_count.append(w_count[i-1])
    if a_r[i-1] == 'E':
        e_count.append(e_count[i-1] + 1)
    else:
        e_count.append(e_count[i-1])

w = w_count[1:]
e = list(reversed(e_count[1:]))

sum = 10000000
for i in range(0, n):
    if sum > w[i] + e[i]:
        sum = w[i] + e[i]

print(sum-1)
### BUGGY CODE ###

input()
ans=1
for i in sorted(map(int,input().split())):
    ans*=i
    if ans==0:break
print(int(ans)if ans<=10**18 else -1)

### FIXED CODE ###

input()
ans=1
for i in sorted(map(int,input().split())):
    ans*=i
    if ans>10**18:ans=-1
    if -1<=ans<=0:break
print(int(ans))
### BUGGY CODE ###

x=int(input())
li=[2]
p=1
i=0
prime=False
if x==2:
    print(2)
else:
    while p<x or prime==False:
        prime=True
        p+=2
        for i in range(len(li)):
            if p%li[i]==0:
                prime=False
        if prime:
            li.append(p)
   
    print(p)
    


### FIXED CODE ###

x=int(input())
p=x-1
prime=False
if x==2:
    print(2)
else:
    while prime==False:
        p+=1
        prime=True
        
        for i in range(2,p-1):
            if p%i==0:
                prime=False
        
        
   
    print(p)
### BUGGY CODE ###

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

max_ans = M // N

tmpM = M
insu = {}
tmp = 2
while tmpM != 1:
    if tmpM % tmp == 0:
        insu[tmp] = insu.get(tmp, 0) + 1
        tmpM = tmpM // tmp
        continue
    else:
        if tmp == 2:
            tmp = 3
        elif tmpM // tmp == 1:
            tmp = tmpM
        else:
            tmp += 2

ins = set()
ins.add(1)
for k, v in insu.items():
    tmp = [k ** i for i in range(v + 1)]
    for s in list(ins):
        for t in tmp:
            ans = t * s
            if ans > max_ans:
                break
            ins.add(ans)
# print(ins)
print(max(ins))

### FIXED CODE ###

from itertools import product

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

max_ans = M // N

ans = 1
tmp = 2
tmpM = M
max_prime = int(M ** 0.5)
all_list = []
i = -1
k = 0
div = 2
while tmpM != 1:
    if tmpM % div == 0:
        tmpM = tmpM // div
        if k == 0:
            i += 1
            all_list.append(set())
            all_list[i].add(div ** k)
            k += 1
        all_list[i].add(div ** k)
        k += 1

    else:
        k = 0
        if div == 2:
            div = 3
        elif div > max_prime:
            div = tmpM
        else:
            div += 2

if all_list == []:
    print(1)
    exit()

# print(all_list)
ans = 1

for div_tuple in product(*all_list):
    tmp = 1
    for k in div_tuple:
        tmp *= k
        if tmp > max_ans:
            break
    else:
        ans = max(ans, tmp)

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

N = int(input())
A = input()
a,b = [0]*N,[0]*N
for i in range(N):
  c = A.count(str(i+1))
  a[i] = c*(c-1)//2
  b[i] = (c-1)*(c-2)//2
d = sum(a)
for i in map(int,A.split()): print(d-a[i-1]+b[i-1])

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
a,b,c = [0]*N,[0]*N,[0]*N
for i in As:
  a[i-1] += 1
  b[i-1] = a[i-1]*(a[i-1]-1)//2
  c[i-1] = (a[i-1]-1)*(a[i-1]-2)//2

d = sum(b)
print("\n".join([str(d-b[i-1]+c[i-1]) for i in As]))
### BUGGY CODE ###

n = int(input())
a = list(map(int, [input() for i in range(n)]))

sum = max(a)
for i in range(n):
    if a[i] == max(a):
        b = a[:]
        b.remove(a[i])
        print(max(b))
    else:
        print(sum)

### FIXED CODE ###

n = int(input())
a = list(map(int, [input() for i in range(n)]))

m1 = max(a)
b = sorted(a, reverse = True)
m2 = max(b[1:])

for i in range(n):
    if a[i] == m1:
        print(m2)
    else:
        print(m1)
### BUGGY CODE ###

def comb(n,r,mod):
	'''
	return nCr
	O(min{n-r, r})
	'''
	a=1
	b=1
	r = min(r,n-r)
	for i in range(r):
		a = a*(n-i)%mod
		b = b*(i+1)%mod
	return a*pow(b,mod-2,mod)%mod


N,K = map(int,input().split())
A = [int(x) for x in input().split()]
A.sort()

mod = 10**9+7

l = [[A[0], comb(N-1, K-1, mod=mod)]]
r = [[A[-1], comb(N-1, K-1, mod=mod)]]


for i in range(1,N):
	if N-i-1>=K-1:
		l.append([A[i], comb(N-i-1, K-1,mod=mod)])
for i in range(N-1)[::-1]:
	if i>=K-1:
		r.append([A[i],comb(i, K-1,mod=mod)])


s = 0
t = 0

for i,j in l:
	s = (s+(i*j)%mod)%mod

for i,j in r:
	t = (t+(i*j)%mod)%mod

ans = (t-s)%mod
if ans < 0:
	ans += mod
print(ans)


### FIXED CODE ###



N,K = map(int,input().split())
A = [int(x) for x in input().split()]
A.sort()

mod = 10**9+7


l = 0
r = 0
t = 1
cnt = 1
for i in range(N-K+1)[::-1]:
	l = (l+(t*A[i])%mod)%mod
	t = (t*(cnt+K-1))%mod
	t = (t*pow(cnt,mod-2, mod))%mod
	cnt+=1
t = 1
cnt = 1
for i in range(K-1, N):
	r = (r+(t*A[i])%mod)%mod
	t = (t*(cnt+K-1))%mod
	t = (t*pow(cnt,mod-2, mod))%mod
	cnt+=1


ans = (r-l)%mod
if ans < 0:
	ans += mod
print(ans)
### BUGGY CODE ###

ｋ = int(input())
a,b = map(int,input().split())
n=0
while True:
    n+=k
    if n>=a and n<=b:
        print('OK')
        break
    if n>b:
        print('NG')

### FIXED CODE ###

ｋ = int(input())
a,b = map(int,input().split())
n=0
while True:
    n+=k
    if n>=a and n<=b:
        print('OK')
        break
    if n>b:
        print('NG')
        break
### BUGGY CODE ###

N = int(input())
S = input()
 
counter = len(S)
 
for i in range(len(S)):
  cost = S[:i].count('W') + S[i+1:].count('E')
  if cost < counter:
    counter = cost
print(counter)

### FIXED CODE ###

N = int(input())
S = input()
W = S.count('W')
E = S.count('E')
counter = len(S)
cost = E
for i in range(len(S)):
  if S[i] == 'E':
    cost -= 1
    if cost < counter:
      counter = cost
  else:
    if cost < counter:
      counter = cost
    cost +=1
print(counter)