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

n = int(input())
listN = [i+1 for i in range(n)]
listM = [j+2 for j in range(n-1)]
listM.append(1)
ans = [x%y for (x,y) in zip(listN,listM)]
print(sum(ans))


### FIXED CODE ###

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

N = int(input())
sums = [1]  # pair number sum until index
cpos = [-1] * (2 * 10 ** 5 + 1)    # positions of each color
#cpos = [-1] * (10)
lastc = -1  # last color of input
C = []      # color stone list
for i in range(N):
    c = int(input())
    if(lastc != c):
        lastc = c
        C.append(c)
        cnt = len(C)
#        print("lastc = {}, cnt = {}, C = {}".format(lastc, cnt, C))
        if(-1 == cpos[c]):
            cpos[c] = [cnt]
            sums.append(sums[-1])
        else:
            s = sums[-1]
            for pos in cpos[c]:
                s += sums[pos - 1]
            sums.append(s)
            cpos[c].append(cnt)
#        print("cpos = " + str(cpos))

#print("C = " + str(C))
#print("cpos = " + str(cpos))
#print("sums = " + str(sums))

print(sums[-1] % (10 ** 9 + 7))


### FIXED CODE ###

sums = [1]  # pair number sum until index
csums = {}  # pair number sum of each color

N = int(input())
C = []      # color stone list
lastc = -1  # last color of input
for i in range(N):
    c = int(input())
    if(lastc == c):
        continue
    lastc = c
    C.append(c)

#print("C = " + str(C))

for i, c in enumerate(C, 1):
    if(c in csums):
        sums.append(sums[-1] + csums[c])
        csums[c] += sums[i - 1]
    else:
        sums.append(sums[-1])
        csums[c] = sums[i - 1]

#    print("i = {}, c = {}".format(i, c))
#    print("csums = " + str(csums))
#    print("sums = " + str(sums))

print(sums[-1] % (10 ** 9 + 7))
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=[str(l.index(i)+1) for i in range(1,n+1)]
print (" ".join(ans))

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=[None]*n
i=1
for index in l:
  ans[index-1]=str(i)
  i+=1
print (" ".join(ans))
### BUGGY CODE ###

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

b = sorted(a,reverse=True)

def binary_search(x):
    l,r = 0,n-1
    while l+1<r:
        i = (l+r)//2
        if b[i] > x:
            l = i
        else:
            r = i
    if abs(b[l]-x)>=abs(b[l+1]-x):
        l += 1
    return b[l]

def comb(n,r):
    r = min(r,n-r)
    ret = 1
    for i in range(1,r+1):
        ret *= (n+1-i)
        ret /= i
    return int(ret)

ans = ""
m = 0
for c in b[:1]:
    if m > c**(c//2):
        break
    r = binary_search(c/2)
    comb_c_r = comb(c,r)
    if m < comb_c_r:
        m = comb_c_r
        ans = str(c)+" "+str(r)
print(ans)

### FIXED CODE ###

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

b = sorted(a,reverse=True)

def binary_search(x):
    l,r = 0,n-1
    while l+1<r:
        i = (l+r)//2
        if b[i] > x:
            l = i
        else:
            r = i
    if abs(b[l]-x)>=abs(b[l+1]-x):
        l += 1
    return b[l]

def comb(n,r):
    r = min(r,n-r)
    ret = 1
    for i in range(1,r+1):
        ret *= (n+1-i)
        ret /= i
    return int(ret)

ans = ""
m = 0
for c in b[:1]:
    r = binary_search(c/2)
    #comb_c_r = comb(c,r)
    #if m < comb_c_r:
        #m = comb_c_r
    ans = str(c)+" "+str(r)
print(ans)
### BUGGY CODE ###

def maximum(l,ind):
	max=-90000000
	for i in range(0,len(l)):
		if(i!=ind):
			if(l[i]>max):
				max=l[i]
	return max
n=int(input())
l=[]
for i in range(0,n):
	l.append(int(input()))
for i in range(0,n):
	print(maximum(l,i))

### FIXED CODE ###

n=int(input())
l=[]
for i in range(n):
	l.append(int(input()))
copy=sorted(l,reverse=True)
for i in range(n):
	if(copy[0]==l[i]):
		print(copy[1])
	else:
		print(copy[0])
### BUGGY CODE ###

N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
qlist = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    qlist[p-1] += x

g = 10**6
cnt = [-1]*N
q = [qlist[0]*g]
cnt[0] = qlist[0]
while q:
    temp = q.pop(0)
    c = temp//g
    v = temp%g
    for i in L[v]:
        if cnt[i] < 0:
            q.append((c+qlist[i])*g + i)
            cnt[i] = c+qlist[i]
            
for i in range(N):
    print(cnt[i])

### FIXED CODE ###

N,Q = map(int, input().split())
L = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    L[a-1].append(b-1)
    L[b-1].append(a-1)
cnt = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x

flag = [1]*N
q = [0]
while q:
    temp = q.pop()
    flag[temp] = 0
    for i in L[temp]:
        if flag[i]:
            q.append(i)
            cnt[i] += cnt[temp]
            
print(*cnt)
### BUGGY CODE ###

import collections

def get_input_line():
    return list(map(int, input().split()))
n, k = get_input_line()
p_list = get_input_line()

def calc_dice_score(p):
    return 0.5*(p+1)

def calc_score(score_list):
    return sum(score_list)

dice_scores = [0.5*(p+1) for p in p_list]

max_score = 0

for i in range(n- k + 1):
    max_score = max(max_score, sum(dice_scores[i:i+k]))
print(max_score)

### FIXED CODE ###

import collections

def get_input_line():
    return list(map(int, input().split()))
n, k = get_input_line()
p_list = get_input_line()

def calc_dice_score(p):
    return 0.5*(p+1)

def calc_score(score_list):
    return sum(score_list)

dice_scores = [0] * n

max_score = 0
tmp_score = 0

for i in range(k):
    dice_scores[i] = 0.5*(p_list[i]+1)
    tmp_score += dice_scores[i]

max_score = tmp_score
for i in range(1, n- k + 1):
    dice_scores[i+k-1] = 0.5*(p_list[i+k-1]+1)
    tmp_score -= dice_scores[i-1]
    tmp_score += dice_scores[i+k-1]
    max_score = max(max_score, tmp_score)
print(max_score)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = a[0]

for i in range(1, n):
    ans *= a[i]


if ans <= 10 ** 18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = a[0]

if 0 in a:
    ans = 0
else:
    for i in range(1, n):
        if ans <= 10 ** 18:
            ans *= a[i]
        else:
            break

if ans <= 10 ** 18:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

def main():
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-1, -1, -1):
            if dp[j] >= 0 and j+w <= W:
                dp[j+w] = max(dp[j+w], dp[j] + v)

    print(max(dp))


main()


### FIXED CODE ###

def main():
    N, W = map(int, input().split())
    wv = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(W+1)
    dp[0] = 0
    for w, v in wv:
        for j in range(W-1, -1, -1):
            if dp[j] >= 0 and j+w <= W:
                dp[j+w] = max(dp[j+w], dp[j] + v)

    print(max(dp))


main()
### BUGGY CODE ###

a = input()
n = len(a)
s = int(a)

m = 0
for i in range(n):
  for j in range(n-i):
    if int(a[i:i+j+1])%2019 == 0:
      m = m+1
print(m)
    

### FIXED CODE ###

m = 2019
s = 0
i = 1
l=[0]*m

for c in reversed(input()):
    s = (s + int(c)* i)%m
    l[s] +=1
    i = (i*10)%m
    
print(l[0] + sum(v*(v-1)//2 for v in l))
### BUGGY CODE ###

n,m = map(int,input().split(" "))
a=[]
mod = 10 ** 9 + 7
ans = 1
for i in range(m):
    a.append(int(input()))
    if a[i]-1 == a[i-1]:
        ans = 0

dp = [1] * (n+1)
for j in range(n+1):
    if j in a:
        dp[j] = 0
    elif j > 1:
        dp[j] = dp[j-1] + dp[j-2]

print(dp[n]%mod)


### FIXED CODE ###

n,m = map(int,input().split(" "))
a=[0] * (n+1)
mod = 10 ** 9 + 7
for i in range(m):
    a[int(input())] = 1

dp = [0] * (n+1)
for j in range(n+1):
    if a[j] == 1:
        dp[j] = 0
    elif j == 1 or j == 0:
        dp[j] = 1
    else:
        dp[j] = (dp[j-1] + dp[j-2]) % mod

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

n = int(input())

l = 0
r = n-1
hist = []
print(0)
hist.append(0)
current = input()

while r - l > 2:
    mid = (l+r)//2
    print(mid)
    hist.append(mid)
    nex = input()
    if nex == 'Vacant':
        exit()
    if current == nex:
        l = mid
    else:
        r = mid
    current = nex

cand = [i for i in range(l, r+1) if i not in hist]
for i in cand:
    print(i)
    nex = input()
    if nex == 'Vacant':
        exit()

### FIXED CODE ###

import sys

n = int(input())
print(0)
sys.stdout.flush()
ls = input()
if ls == 'Vacant':
    exit()
print(n - 1)
sys.stdout.flush()
if input() == 'Vacant':
    exit()
l = 0
r = n - 1
while l != r - 1:
    mid = (l + r) // 2
    if mid % 2 == 1:
        mid += 1
    if mid == r:
        mid -= 1
    print(mid)
    sys.stdout.flush()
    nex = input()
    if nex == 'Vacant':
        exit()

    if ls == nex:
        l = mid
    else:
        r = mid
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = [input().rstrip()[::-1] for i in range(N)]
S.sort(key=lambda x:-len(x))
P = 2**61 - 1

from collections import defaultdict,Counter
D = defaultdict(lambda: Counter())

ans = 0
for s in S:
    a = 0
    for c in s:
        i = ord(c) - ord('a') + 1
        a *= 27
        a += i
        a %= P
    if a in D[len(s)-1]:
        ans += D[len(s)-1][a]
    sets = [0]
    for c in s[::-1]:
        i = ord(c) - ord('a')
        sets.append(sets[-1] | (1<<i))
    sets.reverse()
    a = 0
    for l,(c,st) in enumerate(zip(s,sets)):
        for j in range(26):
            if st&(1<<j):
                na = (a*27 + (j+1)) % P
                D[l][na] += 1
        i = ord(c) - ord('a') + 1
        a *= 27
        a += i
        a %= P

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = [input().rstrip()[::-1] for i in range(N)]
S.sort(key=len)
P = 2**61 - 1

from collections import defaultdict
D = defaultdict(lambda: [0]*26)

ans = 0
for s in S:
    l = ord(s[-1]) - ord('a')
    a = 0
    tmp = [0] * 26
    for c in s[:-1]:
        i = ord(c) - ord('a')
        if a in D:
            for j in range(26):
                tmp[j] += D[a][j]
        ans += tmp[i]
        tmp[i] = 0
        a = (a*27 + i + 1) % P
    ans += tmp[l]
    D[a][l] += 1

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

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

INF = float('inf')
shortest = [[INF]*N for i in range(N)]

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if Map[i][k] == 0 or Map[k][j] == 0:
                continue

            if Map[i][k] + Map[k][j] < Map[i][j]:
                print(-1)
                exit()

            elif Map[i][k] + Map[k][j] == Map[i][j]:
                ans -= Map[i][j]

for m in Map:
    ans += sum(m)

print(ans // 2)

### FIXED CODE ###

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

ans = sum([sum(Map[i]) for i in range(N)])

for k in range(N):
    for i in range(N):
        for j in range(N):
            if Map[i][k] + Map[k][j] < Map[i][j]:
                print(-1)
                exit()

for i in range(N):
    for j in range(N):
        for k in range(N):
            if i == k or j == k:
                continue
            if Map[i][k] + Map[k][j] == Map[i][j]:
                ans -= Map[i][j]
                break

print(ans//2)
### BUGGY CODE ###

import heapq

xs,ys,xt,yt = map(int,input().split())

N = int(input())

xyr = []
xyr.append([xs,ys,0])

#0からN+1までの距離

for i in range(N):

    x,y,r = map(int,input().split())
    xyr.append([x,y,r])

xyr.append([xt,yt,0])

d = [[float("inf")] * (N+2) for i in range(N+2) ]

for i in range(N+2):

    for j in range(N+2):

        nowd = ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5
        nowd = max ( 0 , nowd - xyr[i][2] - xyr[j][2] )

        d[i][j] = nowd
        d[j][i] = nowd

ans = [float("inf")] * (N+2)
ans[0] = 0

q = [[0,0]]

while len(q) > 0:

    np = heapq.heappop(q)
    now = np[1]

    if now == N+1:
        break

    if ans[now] != np[0]:
        continue

    for i in range(N+2):
        if ans[i] > ans[now] + d[now][i]:
            ans[i] = ans[now] + d[now][i]
            heapq.heappush(q,[ans[i] , i])

#print (ans)
print (ans[-1])
    


### FIXED CODE ###

import heapq

xs,ys,xt,yt = map(int,input().split())

N = int(input())

xyr = []
xyr.append([xs,ys,0])

#0からN+1までの距離

for i in range(N):

    x,y,r = map(int,input().split())
    xyr.append([x,y,r])

xyr.append([xt,yt,0])

d = [[float("inf")] * (N+2) for i in range(N+2) ]

for i in range(N+2):

    for j in range(N+2):

        nowd = ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5
        nowd = max ( 0 , nowd - xyr[i][2] - xyr[j][2] )

        d[i][j] = nowd
        d[j][i] = nowd

ans = [float("inf")] * (N+2)
ans[0] = 0
used = [False] * (N+2)

while True:

    v = -1

    #未到達の点に関して最も数値の小さい点を選ぶ
    for i in range(N+2):
        if not used[i] and (v == -1 or ans[v] > ans[i]):
            v = i
    
    if v == -1:
        break
    
    used[v] = True
    for i in range(N+2):
        ans[i] = min(ans[i] , ans[v] + d[v][i])

#print (used,ans)
print (ans[-1])
### BUGGY CODE ###

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    modsum = 0
    for j in range(L):
        count_ones = 0
        count_zeros = 0
        for i in range(N):
            count_ones = count_ones + ((A[i] >> j) & 1)
            count_zeros = N - count_ones
        # MODは一度にとる
        modsum +=  (1<<j) * count_zeros * count_ones
        modsum %= MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


### FIXED CODE ###

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    modsum = 0
    for j in range(L):
        count_ones = sum([1 for a in A if (a >> j) & 1])
        # count_ones = sum([(A[i] >> j) & 1 for i in range(N)])
        count_zeros = N - count_ones
        # MODは一度にとる
        modsum +=  (1<<j) * count_zeros * count_ones
        modsum %= MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
### BUGGY CODE ###

N,M = map(int,input().split())
LRD = [(lambda x: [int(x[0])-1,int(x[1])-1,int(x[2])])(input().split()) for _ in [0]*M]

connect = [[] for _ in range(N)]
for L,R,D in LRD:
    connect[L].append([R,D])
    connect[R].append([L,-D])

n = [None] * N
q = []
n0 = 0
while 1:
    n[n0] = 0
    q.append(n0)
    for i in q:
        for j,d in connect[i]:
            if n[j] == None:
                n[j] = n[i] + d
                q.append(j)
    for i in range(n0,N):
        if n[i] == None:
            n0 = i
            break
    else:
        break

ans = True
for L,R,D in LRD:
    if n[R]-n[L]!= D:
        ans = False
        break
if ans:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N,M = map(int,input().split())
LRD = [(lambda x: [int(x[0])-1,int(x[1])-1,int(x[2])])(input().split()) for _ in [0]*M]

connect = [[] for _ in range(N)]
for L,R,D in LRD:
    connect[L].append([R,D])
    connect[R].append([L,-D])

ans = True
n = [None] * N
n0 = 0
while ans:
    q = [n0]
    n[n0] = 0
    for i in q:
        for j,d in connect[i]:
            if n[j] == None:
                n[j] = n[i] + d
                q.append(j)
            elif n[j]-n[i] != d:
                ans = False
                break
        if not ans:
            break
    for i in range(n0,N):
        if n[i] == None:
            n0 = i
            break
    else:
        break

if ans:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
 
position = 1
exp = [1]
count = 0
 
if n >= k:
  for i in range(k):
    position = a[position - 1]
  print(position)
else:
  for i in range(k):
    position = a[position - 1]
    count += 1
    if not position in exp:
      exp.append(position)
    else:
      break
  init = exp.index(position)
  res = (k - init) % (count - init)
  print(exp[init + res])

### FIXED CODE ###

n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
 
position = 1
exp1 = [0] * n
exp1[0] = 1
exp = [1]
count = 0
 
if n >= k:
  for i in range(k):
    position = a[position - 1]
  print(position)
else:
  for i in range(k):
    position = a[position - 1]
    count += 1
    if exp1[position - 1] == 0:
      exp.append(position)
      exp1[position - 1] += 1
    else:
      break
  init = exp.index(position)
  res = (k - init) % (count - init)
  print(exp[init + res])
### BUGGY CODE ###

import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


class LinkedList:
    def __init__(self, val, pre):
        self.prev = pre
        self.value = val


s = input()
t = input()

info = deque(deque() for _ in range(26))
check = []
for i in range(len(s)):
    info[ord(s[i]) - 97].appendleft(i)
ans = [INF] * (max(len(s), len(t)) + 10)
link = [0] * (max(len(s), len(t)) + 10)
for i in t:
    for l in info[ord(i) - 97]:
        ind = bisect_left(ans, l)
        ans[ind] = l
        a = LinkedList(i, link[ind-1])
        link[ind] = a
num = bisect_left(ans, INF)
ans = deque()
a = link[num-1]
while len(ans) < num:
    ans.appendleft(a.value)
    a = a.prev
print("".join(ans))

### FIXED CODE ###

import sys
import math
from collections import deque
import copy

input = sys.stdin.readline

s = input()
t = input()

dp = [[0 for _ in range(len(t) + 10)] for _ in range(len(s) + 10)]

for i in range(1, len(s)):
    for l in range(1, len(t)):
        if s[i - 1] == t[l - 1]:
            dp[i][l] = max(max(dp[i - 1][l - 1] + 1, dp[i][l - 1]), dp[i - 1][l])
        else:
            dp[i][l] = max(dp[i][l - 1], dp[i - 1][l])
length = dp[len(s) - 1][len(t) - 1]
if length == 0:
    print("")
else:
    ans = ''
    i = len(s) - 1
    l = len(t) - 1
    while i > 0 and l > 0:
        if dp[i-1][l] == dp[i][l] and i >= 1:
            i -= 1
        elif dp[i][l-1] == dp[i][l] and l >= 1:
            l -= 1
        else:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

class Node():
    def __init__(self, key, prev=None, nex=None):
        self.key = key
        self.prev = prev
        self.next = nex
    
class DoublyLinkedLiset():
    def __init__(self):
        self.nil = Node(None)
        self.nil.next = self.nil
        self.nil.prev = self.nil
    
    def insert(self, x):
        X = Node(x)
        X.next = self.nil.next
        self.nil.next.prev = X
        self.nil.next = X
        X.prev = self.nil

    def listSearch(self, x):
        cur = self.nil.next
        while (cur != self.nil and cur.key != key):
            cur = cur.next
        
        return cur

    def deleteNode(self, X):
        if X == self.nil:
            return
        X.prev.next = X.next
        X.next.prev = X.prev
        #del X

    def deleteFirst(self):
        self.deleteNode(self.nil.next)

    def deleteLast(self):
        self.deleteNode(self.nil.prev)

    def deleteKey(self, x):
        self.deleteNode(self.listSearch(x))

    def printList(self):
        cur = self.nil.next
        ret = []
        
        while cur.key is not None:
            ret.append(cur.key)
            cur = cur.next
  
        return ' '.join(ret)

if __name__ == '__main__':

    n = int(input())
    dll = DoublyLinkedLiset()

    for i in range(n):
        line = input().split(" ")
        if len(line) == 2:
            command, key = line
            if command == "insert":
                dll.insert(key)
            elif command == "delete":
                dll.deleteKey(key)

        else:
            command = line[0]
            if command == "deleteFirst":
                dll.deleteFirst()
            elif command == "deleteLast":
                dll.deleteLast()

    print(dll.printList())
    



### FIXED CODE ###

# -*- coding: utf-8 -*-

from collections import deque

if __name__ == '__main__':
    n = int(input())
    L = deque()

    for _ in range(n):
        command = input().split(" ")
        if command[0] == "insert":
            L.appendleft(command[1])
        elif command[0] == "delete":
            try:
                L.remove(command[1])
            except:
                pass
        elif command[0] == "deleteFirst":
            L.popleft()
        elif command[0] == "deleteLast":
            L.pop()

    print(" ".join(L))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

sum = 0
while len(n) > 1:
    sum += int(n[0])
    n = n[1:]

sum += int(n[0])
if sum % 9 == 0:
    print("Yes")
else:
    print("No")


# print("{}".format(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-

# Input#
n = list(input())
# n, k = map(int, input().split())
# a = list(map(int, input().split()))
sum = 0
for i in n:
    sum += int(i)

if sum % 9 == 0:
    print("Yes")
else:
    print("No")


# print("{}".format(ans))
### BUGGY CODE ###

H, W = list(map(int, input().split()))
grid = []
for _ in range(H):
    grid.append(list(input()))
dist_grid = [[-1 for _ in range(W)] for __ in range(H)]

queue = [(0, 0, 1)]
while queue:
    h, w, cnt = queue.pop(0)
    dist_grid[h][w] = cnt
    nexts = [(h+1, w, cnt+1), (h-1, w, cnt+1), (h, w+1, cnt+1), (h, w-1, cnt+1)]
    for y, x, c in nexts:
        if y < 0 or H <= y or x < 0 or W <= x:
            continue
        if dist_grid[y][x] == -1 and grid[y][x] == '.':
            queue.append((y, x, c))
            
sharp_num = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            sharp_num += 1

if dist_grid[-1][-1] == -1:
    print(-1)
else:
    print(H * W - dist_grid[-1][-1] - sharp_num)





### FIXED CODE ###

import sys
from collections import deque
 
h,w = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline()) for _ in range(h)]
dis = [[-1 for _ in range(w)] for _ in range(h)]
 
que = deque()
que.append((0,0))
dis[0][0] = 1
 
while que:
    y,x = que.popleft()
    for dx, dy in ((1,0), (0,1), (-1, 0), (0, -1)):
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (maze[ny][nx] == '.') and (dis[ny][nx] == -1):
            dis[ny][nx] = dis[y][x] + 1
            que.append((ny, nx))
 
ans = 0
black_num = 0
for m in maze:
    black_num += m.count('#')
 
if dis[h-1][w-1] == -1:
    ans = -1
else:
    ans = w*h - black_num - dis[h-1][w-1]
 
print(ans)
### BUGGY CODE ###

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

ans = 0

while N > 0:
    red = min(N, A)
    ans += red
    N -= red
    blue = min(N, B)
    N -= blue
print(ans)


### FIXED CODE ###

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

rep = N//(A+B)
ans = A*rep
diff = N - (A+B)*rep
ans += min(diff, A)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# D - Triangles
N = int(input())
L = list(map(int, input().split()))
L.sort()

triangles = set()

for i in range(N - 2):
	for j in range(i + 1, N - 1):
		for k in range(j + 1, N):
			a = L[i]
			b = L[j]
			c = L[k]			
			
			if b < c + a and c < a + b:
				arr = [a, b, c]
				triangles.add(' '.join(map(str, arr)))
			else:
				break

print(len(triangles))

### FIXED CODE ###

import sys
input = sys.stdin.readline

# D - Triangles
def binary_search(i, j):
	global N

	left = j
	right = N
	
	while right - left > 1:
		mid = (left + right) // 2
		
		if is_match(mid, i, j):
			left = mid
		else:
			right = mid
	
	return left
		

def is_match(mid, i, j):
	global L
	
	a = L[i]
	b = L[j]
	c = L[mid]
	
	if b < c + a and c < a + b:
		return True
	else:
		return False


N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0

for i in range(N - 2):
	for j in range(i + 1, N - 1):
		k = binary_search(i, j)
		
		if k > j and k < N:
			ans += k - j
			
print(ans)