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

k, s=map(int, input().split())
count=0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x>s or y>s or z>s or x+y>s or x+z>s or y+z>s:
        continue
      elif x+y+z==s:
        count+=1
print(count)

### FIXED CODE ###

k, s=map(int, input().split())
count=0
for x in range(k+1):
  for y in range(k+1):
    z=s-x-y
    if 0<=z<=k:
      count+=1
      
print(count)
### BUGGY CODE ###

#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
raw = []
for _ in range(q):
  g,a,b = input().split()
  g = int(g)
  if g == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([g,a,b])
def plus(d,e,j):
  e += 2**scale
  while e != 0:
    seg[d][e] += j
    e //= 2
def sun(d,e):
  if e == -1:
    return 0
  e += 2**scale
  r = seg[d][e]
  while e != 1:
    if e % 2 == 1:
      r += seg[d][e-1]
    e //= 2
  return r
for p in range(q):
  g,a,b = raw[p]
  if g == 1:
    c = t[a]
    plus(c,a,-1)
    t[a] = b
    plus(b,a,1)
  else:
    ans = 0
    for d in range(26):
      if sun(d,a) != sun(d,b):
        ans += 1
    print(ans)
#print(t)

### FIXED CODE ###

#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp >>= 1
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp >>= 1
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp & 1:
            l += seg[d][tmp-1]
          tmp >>= 1
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp & 1:
          r += seg[d][tmp-1]
        tmp >>= 1
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)
### BUGGY CODE ###

l,r = map(int,input().split())

mod = 2019
ans = 10000
for i in range(l,r):
	for j in range(i+1,r+1):
		ans = min(ans,(i*j)%mod)

print(ans)

### FIXED CODE ###

import sys
l,r = map(int,input().split())

mod = 2019
ans = 10000
a = []
for i in range(l,r+1):
  a.append(i%2019)
  if len(a) == 2020*2:
    break


for i in range(len(a)):
	for j in range(len(a)):
		if i == j:
			continue
		ans = min(ans,(a[i]*a[j])%mod)
		if ans == 0:
			print(ans)
			sys.exit()

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

N=int(input())
listA=[input() for i in range(N)]
listB=[]
[x for x in listA if not x in listB and listB.append(x)]
print(len(listB))

### FIXED CODE ###

N=int(input())
listA=[input() for i in range(N)]
listB=set(listA)
print(len(listB))
### BUGGY CODE ###

N, M = map(int, input().split())
p = 10**9 + 7

fac = [0] * (N + 33)
inv = [0] * (N + 33)
finv = [0] * (N + 33)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

for i in range(2, N+33):
  fac[i] = fac[i-1] * i % p
  inv[i] = p - inv[p%i] * (p // i) % p
  finv[i] = finv[i-1] * inv[i] % p

primes = {}
i = 2
while(M > 1):
  if(M % i == 0):
    primes[i] = primes.get(i, 0) + 1
    M //= i
  else:
    i += 2 - (i + 1) % 2
r = 1
for v in primes.values():
  r = r * fac[N+v-1] * finv[N-1] * finv[v] % p
print(r)

### FIXED CODE ###

N, M = map(int, input().split())
p = 10**9 + 7

fac = [0] * (N + 33)
inv = [0] * (N + 33)
finv = [0] * (N + 33)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

for i in range(2, N+33):
  fac[i] = fac[i-1] * i % p
  inv[i] = p - inv[p%i] * (p // i) % p
  finv[i] = finv[i-1] * inv[i] % p

primes = {}
i = 2
while(M > 1):
  if(M % i == 0):
    primes[i] = primes.get(i, 0) + 1
    M //= i
  else:
    i += 2 - (i + 1) % 2
r = 1
for v in primes.values():
  r = r * fac[N+v-1] * finv[N-1] * finv[v] % p
print(r)
### BUGGY CODE ###

from heapq import *
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n=int(input())
aa=LLI(n)

def main():
    ans=sum(sum(ar) for ar in aa)//2
    for w in range(n):
        for u in range(n):
            if u==w:continue
            aau=aa[u]
            for v in range(u):
                if v==w:continue
                d=aau[w]+aa[w][v]
                if d<aau[v]:
                    print(-1)
                    exit()
                if d==aau[v]:
                    ans-=d
    print(ans)

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n=int(input())
aa=LLI(n)

def main():
    ans=sum(sum(ar) for ar in aa)//2
    fin=set()
    for w in range(n):
        aaw=aa[w]
        for u in range(n):
            if u==w:continue
            aau=aa[u]
            for v in range(u):
                if v==w:continue
                d=aau[w]+aaw[v]
                if d<aau[v]:
                    print(-1)
                    exit()
                if d==aau[v] and (u,v) not in fin:
                    ans-=d
                    fin.add((u,v))
    print(ans)

main()
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
MOD = pow(10, 9) + 7

N, K, *A = map(int, read().split())
A_pos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
elif len(A_neg) == N and K % 2 == 1:
    A = sorted(A, key=lambda x: abs(x))
    ans = 1
    for a in A[:K]:
        ans *= a
        ans %= MOD

else:
    A_pos = sorted(A_pos, key=lambda x: -abs(x))
    A_neg = sorted(A_neg, key=lambda x: -abs(x))
    ans = 1
    cnt = 0
    while True:
        if len(A_pos) > 1:
            acc_pos = A_pos[0] * A_pos[1]
        else:
            acc_pos = 0

        if len(A_neg) > 1:
            acc_neg = A_neg[0] * A_neg[1]
        else:
            acc_neg = 0

        if acc_pos > acc_neg or cnt == K - 1:
            if len(A_pos) > 0:
                ans *= A_pos[0]
                A_pos = A_pos[1:]
            else:
                ans *= A_neg[0]
                A_neg = A_neg[1:]
            ans %= MOD
            cnt += 1
        else:
            ans *= acc_neg
            ans %= MOD
            A_neg = A_neg[2:]
            cnt += 2

        if cnt == K:
            break

print(ans % MOD)


### FIXED CODE ###

#! /usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
MOD = pow(10, 9) + 7

N, K, *A = map(int, read().split())

if K == N:
    ans = 1
    for a in A:
        ans = ans * a % MOD
    print(ans)
    sys.exit()

A_pos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

if len(A_pos) == 0:
    if K % 2 == 1:
        A_neg.sort(reverse=True)
    else:
        A_neg.sort()
    ans = 1
    for a in A_neg[:K]:
        ans = ans * a % MOD
    print(ans)
    sys.exit()

A_pos.sort()
A_neg.sort(reverse=True)
ans = 1
r = K
if r % 2 == 1:
    ans = ans * A_pos.pop() % MOD
    r -= 1

while r > 0:
    if len(A_pos) <= 1:
        ans = ans * A_neg.pop() * A_neg.pop() % MOD
    elif len(A_neg) <= 1:
        ans = ans * A_pos.pop() * A_pos.pop() % MOD

    else:
        acc_pos = A_pos[-1] * A_pos[-2]
        acc_neg = A_neg[-1] * A_neg[-2]

        if acc_pos > acc_neg:
            ans = ans * A_pos.pop() * A_pos.pop() % MOD
        else:
            ans = ans * A_neg.pop() * A_neg.pop() % MOD
    r -= 2
print(ans % MOD)
### BUGGY CODE ###

import sys
s = input()
t = input()
for c in set(t):
  if s.find(c) == -1:
    print(-1)
    sys.exit()
p = 0
slen = len(s)
for i in range(1, 10 ** 5 + 1):
  for j in range(slen):
    if s[j] == t[p]:
      p += 1
      if p == len(t):
        print((i - 1) * slen + j + 1)
        sys.exit()


### FIXED CODE ###

import sys

s = input()
t = input()

tset = set(t)
slen = len(s)

if len(tset - set(s)) != 0:
    print(-1)
    sys.exit()

s2t = [i - ord('a') for i in (s + s).encode('ascii')]
lut = [[-1 for _ in range(slen)] for _ in range(26)]
for c in tset:
  b = ord(c) - ord('a')
  j = 0
  for i in range(slen * 2 - 1, -1, -1):
    if s2t[i] == b:
      j = 0
    else:
      j += 1
    if i < slen:
      lut[b][i] = j

p = 0
for c in t:
  b = ord(c) - ord('a')
  p += lut[b][p % slen] + 1
print(p)
### BUGGY CODE ###

a,b,k=map(int,input().split());*r,=range(a,b+1);print(*sorted({*r[:k]+r[-k:]}))

### FIXED CODE ###

a,b,k=map(int,input().split());r=range(a,b+1);print(*sorted(set(r[:k])|set(r[-k:])),sep='\n')
### BUGGY CODE ###

import numpy as np
words = lambda t : list(map(t, input().split()))

h,w = words(int)
wq = [0] * w

grid = []
grid.append(['#'] * (w+2))
for i in range(h):
    grid.append(np.array(['#'] + list(input()) + ['#']))
grid.append(['#'] * (w+2))
np.array(grid)

l = np.zeros((h+2,w+2))
r = np.zeros((h+2,w+2))
u = np.zeros((h+2,w+2))
d = np.zeros((h+2,w+2))

#for i in range(h+2):
#    print(grid[i])


for i in range(1,h+1):
    for j in range(1,w+1):
        if not grid[i][j] == '#':
            l[i][j] = l[i][j-1]+1
            u[i][j] = u[i-1][j]+1

for i in range(h+1,0,-1):
    for j in range(w+1,0,-1):
        if not grid[i][j] == '#':
            r[i][j] = r[i][j+1]+1
            d[i][j] = d[i+1][j]+1


print(int((l+r+u+d).max()-3))


### FIXED CODE ###

#import numpy as np
words = lambda t : list(map(t, input().split()))



h,w = words(int)
wq = [0] * w

grid = []
for i in range(h):
    grid.append(list(input()))

ans = 0
for i in range(h):
    j = 0
    while j < w:
        #print(i,j, grid[i][j])
        if grid[i][j] == '#':
            wq[j] = 0
            j+=1
            continue
        k = 0
        while j+k < w:
            if grid[i][j+k] == '.':
                k += 1
            else:
                break
        #print(i,j,k)
        if k + h > ans:
            for x in range(j,j+k):
                vplus = 0
                if not wq[x] == 0:
                    vplus = wq[x]
                else:
                    for vi in range(i-1,-1,-1):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                    for vi in range(i+1,h):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                ans = max(ans, vplus+k)
                wq[x] = vplus
        j += k
print(ans)
### BUGGY CODE ###

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

from heapq import heappop, heappush

X,Y,Z,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

sum_list = []
seen_list = set()
ans = []

heappush(sum_list, (-(A[0]+B[0]+C[0]), 0, 0, 0))

while sum_list:
    s, i, j, k = heappop(sum_list)
    
    ans.append(-s)

    if i+1 < len(A) and (i+1, j, k) not in seen_list:
        heappush(sum_list, (-(A[i+1]+B[j]+C[k]), i+1, j, k))
        seen_list.add((i+1, j, k))

    if j+1 < len(B) and (i, j+1, k) not in seen_list:
        heappush(sum_list, (-(A[i]+B[j+1]+C[k]), i, j+1, k))
        seen_list.add((i, j+1, k))

    if k+1 < len(C) and (i, j, k+1) not in seen_list:
        heappush(sum_list, (-(A[i]+B[j]+C[k+1]), i, j, k+1))
        seen_list.add((i, j, k+1))

for i in range(0, K):
    print(ans[i])

### FIXED CODE ###

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

def main():

    from heapq import heappop, heappush, heapify
    X,Y,Z,K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)

    sum_list = []
    seen_list = set()
    ans = []

    heappush(sum_list, (-(A[0]+B[0]+C[0]), 0, 0, 0))
    seen_list.add((0, 0, 0))

    for _ in range(K):
        s, i, j, k = heappop(sum_list)
        
        ans.append(-s)

        if i+1 < len(A) and (i+1, j, k) not in seen_list:
            heappush(sum_list, (-(A[i+1]+B[j]+C[k]), i+1, j, k))
            seen_list.add((i+1, j, k))

        if j+1 < len(B) and (i, j+1, k) not in seen_list:
            heappush(sum_list, (-(A[i]+B[j+1]+C[k]), i, j+1, k))
            seen_list.add((i, j+1, k))

        if k+1 < len(C) and (i, j, k+1) not in seen_list:
            heappush(sum_list, (-(A[i]+B[j]+C[k+1]), i, j, k+1))
            seen_list.add((i, j, k+1))

    for i in range(0, K):
        print(ans[i])

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

#!/usr/bin/env python3
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            return visited[Dh][Dw]
        for j in range(-1, 2):
            new_y = y + j
            if 0 <= new_y < H:
                for k in range(-1, 2):
                    new_x = x + k
                    if 0 <= new_x < W:
                        if maze[new_y][new_x] == "." and j**2 + k**2 == 1 and visited[y][x] < visited[new_y][new_x]:
                            visited[new_y][new_x] = visited[y][x]
                            queue.appendleft([new_y, new_x])
        for j in range(-2, 3):
            new_y = y + j
            if 0 <= new_y < H:
                for k in range(-2, 3):
                    new_x = x + k
                    if 0 <= new_x < W:
                        if maze[new_y][new_x] == "." and j**2 + k**2 != 1 and visited[y][x] < visited[new_y][new_x]:
                            visited[new_y][new_x] = visited[y][x] + 1
                            queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2],
              [0, -2], [-1, 2], [-1, 1], [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)

    print(dist if dist != inf else -1)


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

H, W = map(int,input().split())

table = []
for _ in range(H):
    table.append(["k"] + list(input()) + ["k"])
    
table = [["k"]*(W+2)] + table + [["k"]*(W+2)]

import queue
q = queue.Queue()

min_memo = [[None]*(W+2) for _ in range(H+2)]

for y, r in enumerate(table):
    for x, c in enumerate(r):
        if c == "#":
            q.put([y,x,0])
            min_memo[y][x] = 0

while True:
    if q.empty():
        print(cnt)
        break
    y, x, cnt = q.get()
    for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
        if table[y+dy][x+dx] == ".":
            if min_memo[y+dy][x+dx] == None:
                min_memo[y+dy][x+dx] = cnt+1
                q.put([y+dy, x+dx, cnt+1])


### FIXED CODE ###

from collections import deque

H, W = map(int,input().split())

table = []
for _ in range(H):
    table.append(["k"] + list(input()) + ["k"])
    
table = [["k"]*(W+2)] + table + [["k"]*(W+2)]

q = deque()

min_memo = [[None]*(W+2) for _ in range(H+2)]

all_cnt = 0
for y, r in enumerate(table):
    for x, c in enumerate(r):
        if c == "#":
            q.append([y,x,0])
            min_memo[y][x] = 0
            all_cnt += 1

if all_cnt == H*W:
    print(0)
else:          
    while True:
        y, x, cnt = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            if table[y+dy][x+dx] == ".":
                if min_memo[y+dy][x+dx] == None:
                    min_memo[y+dy][x+dx] = cnt+1
                    q.append([y+dy, x+dx, cnt+1])
                    all_cnt += 1
        if all_cnt >= H*W:
            print(cnt+1)
            break
### BUGGY CODE ###

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


dp = [0] * n
for i in range(k - 1, n):
    for j in range(i + 1 - k, i + 1):
        dp[i] += p[j]

maxs = max(dp)
index = dp.index(maxs)

ans = 0
for l in range(index + 1 - k,index + 1):
    ans += sum([z for z in range(1, p[l] + 1)]) / p[l]

print(ans)

### FIXED CODE ###

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

saikoro = [0] * 1001
for i in range(1, 1001):
    saikoro[i] = (saikoro[i-1] + i)

s = [0] * (n + 1)
for u in range(1,n + 1):
    s[u] = saikoro[p[u - 1]] / p[u - 1] + s[u - 1]

ans = 0
for j in range(k - 1,n):
    ans = max(ans, s[j + 1] - s[j + 1 - k])
 
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse=True)
for _ in range(m):
    arr[0] = arr[0] // 2
    arr = sorted(arr, reverse=True)
print(sum(arr))

### FIXED CODE ###

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse=True)

b = arr[0] // 2
i = 0
while True:
    if m == 0:
        break
    if b <= arr[i]:
        arr[i] = arr[i] // 2
        m -= 1
    else:
        arr = sorted(arr, reverse=True)
        i = 0
        b = arr[0] // 2
        continue
    if i < n-1:
        i += 1
    else:
        i = 0

print(sum(arr))
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                ans += 1

print(ans)

### FIXED CODE ###

Max, Sum = map(int, input().split())

counter = 0
for i in range(Max+1):
  for j in range(Max+1):
    k = Sum - i -j
    if k >= 0 and k <= Max:
      counter += 1
 
print(counter)
### BUGGY CODE ###


def comp(ext,list0,dev):
    if list0[int((ext[0]+ext[1])/2)]>dev:
        return ext[0],int((ext[0]+ext[1])/2)
    else:
        return int((ext[0]+ext[1])/2),ext[1]


def bis(a,b,list0,dev):
    ls=[a,b]
    while ls[0]+1<ls[1]:
        ls=comp(ls,list0,dev)
    if list0[ls[0]]==dev:
        return ls[0]-1
    elif list0[ls[1]]==dev:
        return ls[1]-1
    else:
        return ls[0]


n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(0,n-2):
    for b in range(a+1,n-1):
        if l[a]+l[b]>l[n-1]:
            c=n-1
        elif l[a]+l[b]<l[b+1]:
            c=b
        else:
            c=bis(b+1,n-1,l,l[a]+l[b])
        s=s+c-b
print(s)

### FIXED CODE ###

def bis_right(lis,dev):
    a=0
    b=len(lis)-1
    while a<b:
        c=(a+b)//2
        if lis[c]>dev:
            b=c
        else:
            a=c+1
    if lis[a]<=dev:
        return a
    return a-1



n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(n-2):
    for b in range(a+1,n-1):
        c=bis_right(l[b+1:],l[a]+l[b]-1)
        s+=c+1
print(s)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
mod=10**9+7

dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
      dp[1]=1
for i in range(2,len(dp)):
      if i not in a:
            dp[i]=dp[i-1]+dp[i-2]
      
print(dp[-1]%mod)

### FIXED CODE ###

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

ai=0
n1,n2=0,1
for i in range(1,n+1):
      if ai<m and i==A[ai]:
            ai+=1
            n1=n2
            n2=0
      else:
            tmp=n2
            n2=(n1+n2)%1000000007
            n1=tmp
print(n2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    count = [0] * 2020
    count[0] = 1
    ans = 0
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        v = V[rev_i] + S[i] * pow(10,rev_i+1)
        V[rev_i+1] = v
        u = v % K

        count[u] += 1
        cnt = count[u]
        ans -= (cnt-1) * (cnt-2) // 2
        ans += cnt * (cnt-1) // 2


    print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (pow(10,rev_i+1,K))
        # print(V)

    dic = {} # value:count
    U = set()
    for v in V:
        u = v % K
        if u in U:
            dic[u] += 1
        else:
            dic[u] = 1
            U.add(u)

    ans = 0
    for u in U:
        u_count = dic[u]
        ans += u_count * (u_count-1) // 2

    # print(S)
    # print(V)
    # print(dic)
    print(ans)

if __name__ == "__main__":
  main()