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

import queue
def search(sy,sx,ey,ex):
    global H,W,Maze
    q = queue.Queue()

    Visit = [[-1]*W for _ in range(H)]
    Dir = [[0,1],[0,-1],[1,0],[-1,0]]

    Visit[sy][sx] = 0 
    q.put([sy,sx])

    while not q.empty():
        ty,tx = q.get()
        path = Visit[ty][tx]

        for dy,dx in Dir:
            ny = ty + dy
            nx = tx + dx
            if 0 <= ny and ny < H and 0 <= nx and nx < W:
                if Maze[ny][nx] == '.':
                    if ny == ey and nx == ex:
                        return path+1

                    if Visit[ny][nx] == -1:
                        Visit[ny][nx] = path+1
                        q.put([ny,nx])
    return -1

H,W = map(int,input().split())
Maze = []
for h in range(H):
    Maze.append(input())

ans = 0
for sy in range(H):
    for sx in range(W):
        if Maze[sy][sx] == '#':
            continue
        for ey in range(H):
            for ex in range(W):
                if Maze[ey][ex] == '#':
                    continue
                if sx == ex and sy == ey:
                    continue
                p = search(sy,sx,ey,ex)          
                if p != -1:
                    ans = max(ans,p)
print(ans)


### FIXED CODE ###

import queue
def search(sy,sx):
    global H,W,Maze
    q = queue.Queue()

    Visit = [[-1]*W for _ in range(H)]
    Dir = [[0,1],[0,-1],[1,0],[-1,0]]

    Visit[sy][sx] = 0 
    q.put([sy,sx])

    while not q.empty():
        ty,tx = q.get()
        path = Visit[ty][tx]

        for dy,dx in Dir:
            ny = ty + dy
            nx = tx + dx
            if 0 <= ny and ny < H and 0 <= nx and nx < W:
                if Maze[ny][nx] == '.':
                    if Visit[ny][nx] == -1:
                        Visit[ny][nx] = path+1
                        q.put([ny,nx])
    max1 = 0
    for h in range(H):
        for w in range(W):
            max1 = max(max1,Visit[h][w])
    return max1

H,W = map(int,input().split())
Maze = []
for h in range(H):
    Maze.append(input())

ans = 0
for sy in range(H):
    for sx in range(W):
        if Maze[sy][sx] == '#':
            continue
        p = search(sy,sx)          
        if p > 0:
            ans = max(ans,p)
print(ans)
### BUGGY CODE ###

X, Y = map(int, input().split())

if X == Y:
    print(-1)
    exit()
x = 2
while True:
    if X * x % Y != 0:
        print(X * x)
        exit()
    x += 1


### FIXED CODE ###

X, Y = map(int, input().split())

if X % Y == 0:
    print(-1)
else:
    print(X)
### BUGGY CODE ###

# n, m, l = map(int, input().split())

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import sys
input = sys.stdin.readline

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

start = 0
n = 0
for i in range(N):
    if i + 1 in A[start:]:
        start = len(A[:start]) + A[start:].index(i+1) + 1
        n = i + 1
    else:
        break
if n != 0:
    print(N-n)
else:
    print(-1)


### FIXED CODE ###

# n, m, l = map(int, input().split())

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import sys
input = sys.stdin.readline

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

n = 1
ans = 0
for i in A:
    if i == n:
        n += 1
    else:
        ans += 1
if n == 1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N = int(input())
clis = [];slis =[];flis = []
for i in range(N-1):
    c,s,f = map(int,input().split())
    clis.append(c);slis.append(s);flis.append(f)
for i in range(N):
    count =0
    for i2 in range(N-i-1):
        s = slis[i+i2]
        f = flis[i+i2]
        i3 = 0
        while True:
            if s+f*i3 >= count:
                count = s+f*i3+clis[i+i2]
                break
            i3 += 1
    print(count)


### FIXED CODE ###

N = int(input())
clis = [];slis =[];flis = []
for i in range(N-1):
    c,s,f = map(int,input().split())
    clis.append(c);slis.append(s);flis.append(f)
for i in range(N):
    count=0
    for i2 in range(N-i-1):
        c=clis[i+i2];s=slis[i+i2];f=flis[i+i2]
        if count <= s:
            count=s+c
        elif (count-s)%f ==0:
            count = count+c
        else:
            count = count + c+f-count%f
    print(count)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
default=0
for i in set(a):
    default+=a.count(i)*(a.count(i)-1)//2
for k in a:
    print(default-(a.count(k)-1))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
cnt = 0
for i in c.values():
    cnt += i * (i - 1) // 2
for i in a:
    print(cnt - c[i] + 1)
### BUGGY CODE ###

N,K=map(int, input().split())
a_ls=list(map(int, input().split()))

j=1
step=0
s=set([])
l=[]
loop_s=-1
loop_g=-1

while True:
	s.add(j)
	l+=[j]
	j=a_ls[j-1] #update
	if j in l:
		loop_s=l.index(j)
		loop_g=len(l)
		break


#print(l)
#print(loop_s)
#print(loop_g)

if K<loop_s:
	print(l[K])
elif (K+1-loop_s)%(loop_g-loop_s)!=0:
	print(l[loop_s+(K+1-loop_s)%(loop_g-loop_s)-1])
else:
	print(l[-1])



### FIXED CODE ###

N,K=map(int, input().split())
a_ls=list(map(int, input().split()))

j=1
step=0
s=set([])
l=[]
loop_s=-1
loop_g=-1

while True:
	s.add(j)
	l+=[j]
	j=a_ls[j-1] #update
	if j in s:
		loop_s=l.index(j)
		loop_g=len(l)
		break


#print(l)
#print(loop_s)
#print(loop_g)

if K<loop_s:
	print(l[K])
elif (K+1-loop_s)%(loop_g-loop_s)!=0:
	print(l[loop_s+(K+1-loop_s)%(loop_g-loop_s)-1])
else:
	print(l[-1])
### BUGGY CODE ###

N, A, B, K = tuple(map(int, (input().split())))
mod = 998244353

def ab(n):
    ab = []
    a = n // A
    while (n - A * a) % B != 0:
        a -= 1
    b = (n - A * a) // B
    ab.append((a, b))
    while a > 0:
        a, b = a - B // gcd(A, B), b + A // gcd(A, B)
        if a < 0:
            break
        ab.append((a, b))
    return ab

def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    return gcd(b, a - b * (a // b))

def mpow(x, n):
    ans = 1
    while n != 0:
        if n & 1:
            ans = ans * x % mod
        x = x * x % mod
        n = n >> 1
    return ans

factorial = [1 for i in range(N + 1)]
inverse = [1 for i in range(N + 1)]
for i in range(1, N + 1):
    factorial[i] = (factorial[i - 1] * i) % mod
    inverse[i] = mpow(factorial[i], mod - 2) % mod

com = [((factorial[N] * inverse[r] % mod) * inverse[N - r] % mod) for r in range(0, N + 1)]

ans = 0
for a, b in ab(K):
    if a > N or b > N:
        continue
    ans += com[a] * com[b]
print(ans % mod)

### FIXED CODE ###

N, A, B, K = tuple(map(int, (input().split())))
mod = 998244353

factorial = [1 for i in range(N + 1)]
inverse = [1 for i in range(N + 1)]
for i in range(1, N + 1):
    factorial[i] = (factorial[i - 1] * i) % mod
    inverse[i] = inverse[i - 1] * pow(i, mod - 2, mod) % mod

com = [1 for i in range(N + 1)]
for i in range(1, N + 1):
    com[i] = (factorial[N] * inverse[i] % mod) * inverse[N - i] % mod

ans = 0
for x in range(N + 1):
    d = K - A * x
    if 0 <= d and d % B == 0:
        y = d // B
        if y <= N:
            ans += com[x] * com[y]
print(ans % mod)
### BUGGY CODE ###

I = list(map(int, input().split()))
K, S = I[0], I[1]

count = 0
for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i+j+k == S:
        count += 1
        
print(count)

### FIXED CODE ###

I = list(map(int, input().split()))
K, S = I[0], I[1]

print(len([0 for i in range(K+1) for j in range(K+1) if 0<=S-i-j<=K]))
### BUGGY CODE ###

import sys
input=sys.stdin.readline

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

w = [i for i in range(H*W)]
b = []
i = 0
for h in range(H):
    s = list(input().strip())
    for c in s:
        if c == "#":
            b.append(i)
            w.remove(i)
        i += 1
t = 0
while len(w) > 0:
    """
    print("<<<< %d >>>>" %(t))
    print(b)
    print(w)
    for hh in range(H):
        s = ""
        for ww in range(W):
            if hh*W+ww in b:
                s += "#"
            else:
                s += "."
        print(s)
    """
    t += 1
    tb = []
    for i in b:
        if i-W >= 0 and i-W in w:
            w.remove(i-W)
            tb.append(i-W)
        if i%W > 0 and i-1 in w:
            w.remove(i-1)
            tb.append(i-1)
        if i%W < W-1 and i+1 in w:
            w.remove(i+1)
            tb.append(i+1)
        if i+W < H*W and i+W in w:
            w.remove(i+W)
            tb.append(i+W)
    for i in tb:
        if i not in b:
            b.append(i)
    b.remove(i)
print(t)


### FIXED CODE ###

import sys
input=sys.stdin.readline
H,W = map(int, input().split())

b = [[True]*(W+2)]
for _ in range(H):
    b.append([True] + [x == '#' for x in input().strip()] + [True])
b.append([True]*(W+2))

check = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            check.append((i,j))
t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

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

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, m = map(int, input().split())
  la, lb = [], []
  lc = []
  MAX = 10**9
  dp = [MAX] * (2 ** 13)
  dp[0] = 0
  
  for _ in range(m):
    a, b = map(int, input().split())
    la.append(a)
    lb.append(b)
    lc.append(sum([1 << c for c in map(int, input().split())]))
    
  for a, c in zip(la, lc):
    for ic in range(len(dp)):
      dp[c | ic] = min(a + dp[ic], dp[c | ic])
  if dp[2**(n+1)-2] != MAX:
    print(dp[2**(n+1)-2])
  else:
    print(-1)

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, m = map(int, input().split())
  la, lb = [], []
  lc = []
  MAX = 10**9
  dp = [MAX] * (2 ** 13)
  dp[0] = 0
  
  for _ in range(m):
    a, b = map(int, input().split())
    la.append(a)
    lb.append(b)
    lc.append(sum([1 << c for c in map(int, input().split())]))
    
  for a, c in zip(la, lc):
    for ic in range(len(dp)):
      dp[c | ic] = min(a + dp[ic], dp[c | ic])
  if dp[2**(n+1)-2] != MAX:
    print(dp[2**(n+1)-2])
  else:
    print(-1)

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

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

def get_groups(n, m):
    road = [[] for _ in range(n+1)]
    for _ in range(m):
        p, q = list(map(int, input().split()))
        road[p].append(q)
        road[q].append(p)

    groups = [0]*(n+1)
    group_idx = 1
    for i in range(1, n+1):
        if groups[i] == 0:
            groups[i] = group_idx
            connect = [i]
            while len(connect) > 0:
                cnct = connect[0]
                connect = connect[1:]
                for c in road[cnct]:
                    if groups[c] == 0:
                        groups[c] = group_idx
                        connect.append(c)
            group_idx += 1
            
    return groups

road_groups = get_groups(n, k)
train_groups = get_groups(n, l)
# print(road_groups, train_groups)
pairs = {}
for c in range(1, n+1):
    key = (road_groups[c], train_groups[c])
    if not key in pairs.keys():
        pairs[key] = 1
    else:
        pairs[key] += 1

ans = []
for c in range(1, n+1):
    key = (road_groups[c], train_groups[c])
    ans.append(str(pairs[key]))
print(' '.join(ans))


### FIXED CODE ###

from collections import deque

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

def get_groups(n, m):
    road = [[] for _ in range(n+1)]
    for _ in range(m):
        p, q = list(map(int, input().split()))
        road[p].append(q)
        road[q].append(p)

    groups = [0]*(n+1)
    group_idx = 1
    connect = deque()
    for i in range(1, n+1):
        if groups[i] == 0:
            groups[i] = group_idx
            connect.clear()
            connect.append(i)
            while len(connect) > 0:
                cnct = connect.popleft()
                for c in road[cnct]:
                    if groups[c] == 0:
                        groups[c] = group_idx
                        connect.append(c)
            group_idx += 1
            
    return groups

road_groups = get_groups(n, k)
train_groups = get_groups(n, l)
# print(road_groups, train_groups)
pairs = {}
for c in range(1, n+1):
    key = (road_groups[c], train_groups[c])
    if not key in pairs.keys():
        pairs[key] = 1
    else:
        pairs[key] += 1

ans = []
for c in range(1, n+1):
    key = (road_groups[c], train_groups[c])
    ans.append(str(pairs[key]))
print(' '.join(ans))
### BUGGY CODE ###

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

v1=v[::2]
V1=list(set(v1))
n1=len(V1)
v2=v[1::2]
V2=list(set(v2))
n2=len(V2)

cnt1={}
cnt2={}

for i in range(n1):
  cnt1[V1[i]]=v1.count(V1[i])
for i in range(n2):
  cnt2[V2[i]]=v2.count(V2[i])

max1_k=max(cnt1,key=cnt1.get)
max2_k=max(cnt2,key=cnt2.get)
if max1_k!=max2_k:
  print(N-cnt1[max1_k]-cnt2[max2_k])
else:
  if cnt1[max1_k]>=cnt2[max2_k]:
    if n2==1:
      print(N-cnt1[max1_k])
    else:
      cnt2.pop(max2_k)
      max2_k=max(cnt2,key=cnt2.get)
      print(N-cnt1[max1_k]-cnt2[max2_k])
  else:
    if n1==1:
      print(N-cnt2[max2_k])
    else:
      cnt1.pop(max1_k)
      max1_k=max(cnt1,key=cnt.get)
      print(N-cnt1[max1_k]-cnt2[max2_k])

### FIXED CODE ###

from collections import Counter

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

v1=v[::2]
n1=len(set(v1))
v2=v[1::2]
n2=len(set(v2))

cnt1=Counter(v1)
cnt2=Counter(v2)

cnt1=cnt1.most_common()
cnt2=cnt2.most_common()

if cnt1[0][0]!=cnt2[0][0]:
  print(N-cnt1[0][1]-cnt2[0][1])
else:
  if n1==1 and n2==1:
    print(N-cnt1[0][1])
  elif n1==1:
    print(N-cnt1[0][1]-cnt2[1][1])
  elif n2==1:
    print(N-cnt1[1][1]-cnt2[0][1])
  else:
    print(N-max(cnt1[0][1]+cnt2[1][1],cnt1[1][1]+cnt2[0][1]))
### BUGGY CODE ###

mod = 998244353
def main():
    N,S = map(int,input().split())
    a = list(map(int,input().split()))
    dp = [[[0,0,0] for _ in range(S+1)]for _ in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(S+1):
            dp[i+1][j][0] += dp[i][j][0] ;dp[i+1][j][0] %= mod
            dp[i+1][j][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j][1] %= mod
            dp[i+1][j][2] += dp[i][j][0]+dp[i][j][1]+dp[i][j][2];dp[i+1][j][2]%= mod
            if j+a[i] <= S:
                dp[i+1][j+a[i]][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][1] %= mod
                dp[i+1][j+a[i]][2] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][2] %= mod
    print(dp[N][S][2])
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin
mod = 998244353
def main():
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    dp = [0]*(S+1)
    ans = 0
    for A in a:
        dp[0] += 1
        for i in reversed(range(A,S+1)):
            dp[i] += dp[i-A]    
            dp[i] %= mod
        ans += dp[S]
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

def dfs(l, r, wl, wr):
    if r <= l + 1:
        return 0
    return min(dfs(l, m, wl, wl+wr) + dfs(m, r, wl+wr, wr) + A[m] * (wl+wr) for m in range(l+1, r))

print(dfs(0, N-1, 1, 1) + A[0] + A[N-1])


### FIXED CODE ###

from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

@lru_cache(maxsize=None)
def dfs(l, r, wl, wr):
    if r <= l + 1:
        return 0
    v = min(dfs(l, m, wl, wl+wr) + dfs(m, r, wl+wr, wr) + A[m] * (wl+wr) for m in range(l+1, r))
    return v

print(dfs(0, N-1, 1, 1) + A[0] + A[N-1])
### BUGGY CODE ###

H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  for k in range((r-l)//D):
    x1=A[l+D*k-1][0]
    x2=A[l+D*(k+1)-1][0]
    y1=A[l+D*k-1][1]
    y2=A[l+D*(k+1)-1][1]
    ans+=abs(x1-x2)
    ans+=abs(y1-y2)
  print(ans)
  ans=0

### FIXED CODE ###

H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
S=[[0]*((H*W-1-i)//D+1) for i in range(D)]
for i in range(D):
  for k in range((H*W-1-i)//D):
    x1=A[D*k+i][0]
    x2=A[D*(k+1)+i][0]
    y1=A[D*k+i][1]
    y2=A[D*(k+1)+i][1]
    S[i][k+1]+=S[i][k]+abs(x1-x2)+abs(y1-y2)
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  m=(l-1)%D
  ans=S[m][(r-1-m)//D]-S[m][(l-1-m)//D]
  print(ans)
  ans=0
### BUGGY CODE ###

N = int(input())
x = []
count = 0

for i in range(N):
    a = int(input())
    if a in x:
        x.remove(a)
    else:
        x.append(a)

print(len(x))


### FIXED CODE ###

import collections as cl
N = int(input())
x = []
count = 0

for i in range(N):
    a = int(input())
    x.append(a)

d = cl.Counter(x)

for i in d.values():
    if i % 2 == 1:
        count += 1
print(count)
### BUGGY CODE ###

import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
a = S[-1]
dp = np.zeros((n, 26), int)
x_ = dp[0]
l = [[13 - i * j % 13 for j in range(0, 10)] for i in [1, 10, 9, 12, 3, 4]] * (n // 6 + 1)
if a == "?":
    x_[0:10] += 1
else:
    x_[int(a)] += 1
x_[13:] = x_[:13]
for s, x, l_ in zip(S[-2::-1], dp[1:], l[1:]):
    if s == "?":
        x[:13] += np.sum([x_[v:v+13] for v in l_], axis=0)
    else:
        v = l_[int(s)]
        x[:13] += x_[v:v+13]
    x %= mod
    x[13:] = x[:13]
    x_ = x
print(x_[5])

### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

(N, K) = list(map(int,input().split()))
P = list(map(int, input().split()))

def max_expected(L, K):
  length = len(L)
  if (length < K):
    return -1
  if (length == K):
    return (sum(L) + K) / 2
  mid = length // 2
  s_left = max_expected(L[0:mid], K)
  #print("left array:{}, max: {}".format(L[0:mid], s_left))
  s_right = max_expected(L[mid:], K)
  #print("right array:{}, max: {}".format(L[mid:], s_right))
  offset = 0

  if (mid - K + 1 < 0):
    offset = - (mid - K + 1)
  end_offset = 0
  if (mid + K - 1 >= length):
    end_offset = mid + K - 1 - length
  max_p = sum(L[mid - K + 1 + offset:mid + 1 + offset])
  for i in range(mid - K + 1 + offset, mid - end_offset):
    j = sum(L[i:(i + K)])
    #print("{}[{}]..{}[{}]: {}".format(L[i], i, L[i + K - 1], i + K - 1, j))
    if max_p < j:
      max_p = j
  #print("mid: {}".format((max_p + K) / 2));
  
  return max((max_p + K) / 2, s_left, s_right)
print("{}".format(max_expected(P, K)))

### FIXED CODE ###

(N, K) = list(map(int,input().split()))
P = list(map(int, input().split()))

def max_expected(L, K):
  length = len(L)
  if (length < K):
    return -1
  if (length == K):
    return (sum(L) + K) / 2
  mid = length // 2
  s_left = max_expected(L[0:mid], K)
  s_right = max_expected(L[mid:], K)
  offset = 0

  if (mid - K + 1 < 0):
    offset = - (mid - K + 1)
  end_offset = 0
  if (mid + K - 1 >= length):
    end_offset = mid + K - 1 - length
  max_p = sum(L[mid - K + 1 + offset:mid + 1 + offset])
  prev = max_p
  for i in range(mid - K + 1 + offset + 1, mid - end_offset):
    prev = prev - L[i - 1] + L[i + K - 1]
    if max_p < prev:
      max_p = prev
  
  return max((max_p + K) / 2, s_left, s_right)
print("{}".format(max_expected(P, K)))
### BUGGY CODE ###

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

import itertools
l = list(itertools.combinations(L, 3))

a = 0
n = 0

for x in range(len(l)):
  if max(l[n]) < sum(l[n]) - max(l[n]):
    a += 1
    n += 1
  else:
    n += 1
    
print(a)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
from bisect import bisect_left
for i in range(n-2):
  for j in range(i+1, n-1):
    ab = l[i] + l[j]
    idx = bisect_left(l, ab)
    ans += max(idx-j-1, 0)
print(ans)
### BUGGY CODE ###

import numpy as np


def main():
    N, S = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    dp = np.zeros((N+1, S+1), dtype=np.int64)

    dp[0,0] = 1
    MOD = 998244353
    for i in range(N):
        for j in range(S+1):
            dp[i+1, j] += 2 * dp[i, j]
            dp[i+1, j] %= MOD
            if j + A[i] <= S:
                dp[i+1, j+A[i]] += dp[i, j]
                dp[i+1, j+A[i]] %= MOD
    print(dp[N,S])
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

### FIXED CODE ###

import numpy as np
import numba
from typing import List


@numba.jit
def solver(N: int, S: int, A: np.array) -> int:
    dp = np.zeros((N+1, S+1), dtype=np.int64)

    dp[0,0] = 1
    MOD = 998244353
    for i in range(N):
        for j in range(S+1):
            dp[i+1, j] += 2 * dp[i, j]
            dp[i+1, j] %= MOD
            if j + A[i] <= S:
                dp[i+1, j+A[i]] += dp[i, j]
                dp[i+1, j+A[i]] %= MOD
    return dp[N,S]


def main():
    N, S = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    ans = solver(N, S, np.array(A))
    print(ans)
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()
### BUGGY CODE ###

s = input()
n = len(s)
cnt = [0]*2019
cnt[0] += 1
for i in range(n):
    cnt[int(s[i:])%2019] += 1

'''
slist = [(s%(10**i))%2019 for i in range(n+1)]
#print(slist)
cnt = [0]*2019

for m in slist:
    cnt[m] += 1
'''
ans = 0
for i in range(2019):
    ans += cnt[i]*(cnt[i]-1)//2

print(ans)


### FIXED CODE ###

s = input()[::-1]
a = 0
cnt = [0]*2019
cnt[0] = 1
d = 1
for c in s:
    a += int(c) * d
    a %= 2019
    d *= 10
    d %= 2019
    cnt[a] += 1

#slist = [(s%(10**i))%2019 for i in range(n+1)]
#print(slist)


ans = 0
for i in range(2019):
    ans += cnt[i]*(cnt[i]-1)//2

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

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

count = 0
for x in range(k+1):
  for y in range(k+1):
    if x + y > s:
      break
    a = s - x - y
    if a >= 0 and a <= k:
      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):
    a = s - x - y
    if a >= 0 and a <= k:
      count += 1

print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()]

ans = 1
for i in range(n):
    ans *= a[i]
if ans > pow(10, 18):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()]

ans = 1
a.sort()
for i in range(n):
    ans *= a[i]
    #print(ans)
    if ans > pow(10, 18):
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import numpy as np

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

A = np.array(A_)

ans = 0
for X in range(np.min(A),np.max(A)+1):
    tmp = 0
    for a in A:
        if a == X or a == X+1 or a == X-1:
            tmp += 1
    ans = max(tmp,ans)
print(ans)


### FIXED CODE ###

import collections

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

dic = collections.Counter(A)
tmp = [0 for _ in range(A[-1]+1)]


for X in dic.keys():
    tmp[X] = dic[X]

ans = 0
for i in range(len(tmp)):
    ans = max(ans,sum(tmp[i:i+3]))

print(ans)