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

import heapq
xs, ys, xt, yt = map(int, input().split())
N = int(input())
C = [(xs, ys, 0), (xt, yt, 0)]
C += [tuple(map(int, input().split())) for i in range(N)]

G = [[] for i in range(N+2)]
for i in range(N+2):
    for j in range(i+1, N+2):
        cost = max(0, ((C[i][0] - C[j][0]) ** 2 + (C[i][1] - C[j][1]) ** 2) ** 0.5 - (C[i][2] + C[j][2]))
        G[i].append((j, cost))
        G[j].append((i, cost))


def dijkstra(x):
    d = [float('inf')] * (N + 2)
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


dist = dijkstra(0)
print(dist[1])


### FIXED CODE ###

import sys
import heapq
my_input = sys.stdin.readline

def main():
    xs, ys, xt, yt = map(int, my_input().split())
    N = int(my_input())
    C = [(xs, ys, 0), (xt, yt, 0)]
    C += [tuple(map(int, my_input().split())) for i in range(N)]

    G = [[] for i in range(N+2)]
    for i in range(N + 2):
        for j in range(i + 1, N + 2):
            cost = max(0, ((C[i][0] - C[j][0]) ** 2 + (C[i][1] - C[j][1]) ** 2) ** 0.5 - (C[i][2] + C[j][2]))
            G[i].append((j, cost))
            G[j].append((i, cost))


    def dijkstra(graph, start, inf=float('inf')):
        import heapq
        n = len(graph)
        distances = [inf] * n
        distances[start] = 0
        visited = [False] * n

        # 距離・頂点
        hq = [(0, start)]
        while hq:
            dist, fr = heapq.heappop(hq)
            if distances[fr] < dist:
                continue
            if fr == 1:
                return distances
            visited[fr] = True

            for to, cost in graph[fr]:
                new_dist = distances[fr] + cost
                if (visited[to]) or (distances[to] <= new_dist):
                    continue

                distances[to] = new_dist
                heapq.heappush(hq, (new_dist, to))

        return distances


    dist = dijkstra(G, 0)
    print(dist[1])


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

def main():
    N, *XL = map(int, open(0).read().split())
    # print(N, XL)
    robots = [0]*N
    for i in range(N):
        X, L = XL[2 * i + 0], XL[2 * i + 1]
        robots[i] = (i, X - L, X + L)
    robots.sort(key=lambda x: x[2])
    # print(robots)
    remains = []
    for robot in robots:
        # print('remains={}, robot={}'.format(remains, robot))
        conflict = False
        l = robot[1]
        r = robot[2]
        for remain in remains:
            # print(l, r, remain)
            if remain[1] <= l and l < remain[2]:
                # print(robot, remain, l, remain[2], remain[1], r)
                conflict = True
                break
            if remain[1] < r and r < remain[2]:
                # print(robot, remain, l, remain[2], remain[1], r)
                conflict = True
                break
            if l <= remain[1] and remain[1] < r:
                conflict = True
                break
            if l < remain[2] and remain[2] < r:
                conflict = True
                break
        if not conflict:
            remains.append(robot)
    print(len(remains))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, *XL = map(int, open(0).read().split())
    # print(N, XL)
    robots = [0]*N
    for i in range(N):
        X, L = XL[2 * i + 0], XL[2 * i + 1]
        robots[i] = (X - L, X + L)
    robots.sort(key=lambda x: x[1])
    # print(robots)
    ans = 0
    last = robots[0][0] - 1
    for robot in robots:
        if last <= robot[0]:
            last = robot[1]
            ans += 1

    print(ans)

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

N = int(input())
if N == 1:
  print("0")
else:
  ans = 0
  for i in range(N):
    ans += i
  print(ans)


### FIXED CODE ###

N = int(input())
if N == 1:
  print("0")
else:
  ans = (N * (N-1))//2
  print(ans)
### BUGGY CODE ###

from sys import stdin
s = str(stdin.readline().rstrip())
q = int(stdin.readline().rstrip())
for i in range(q):
    query = list(map(str, stdin.readline().rstrip().split()))
    if len(query)==1:
        #反転
        pass
        s = s[::-1]
    else:
        if int(query[1])==2:
            s += query[2]
        else:
            s = query[2] + s

print(s)


### FIXED CODE ###

from sys import stdin
s = str(stdin.readline().rstrip())
#A, B, C = map(int, stdin.readline().rstrip().split())
#S = [list(map(int, stdin.readline().rstrip().split())) for _ in range(h)]#hの定義を忘れずに
q= int(stdin.readline().rstrip())
hanten = 0
t=""
u=""

for i in range(q):
    l = list(map(str, stdin.readline().rstrip().split()))
    if int(l[0]) == 1:
        t,u = u,t
        hanten ^= 1
    else:
        if int(l[1])==1:
            t+=l[2]
        else:
            u+=l[2]


if hanten==0:
    print(t[::-1]+s+u)
else:
    print(t[::-1]+s[::-1]+u)
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()
    ans = 0
    for i in range(1000):
        key = "0" * (3 - len(str(i))) + str(i)
        j = 0
        flag = True
        while True:
            if j == n:
                flag = False
                break
            if s[j] == key[0]:
                j += 1
                break
            j += 1
        if not flag:
            continue
        while True:
            if j == n:
                flag = False
                break
            if s[j] == key[1]:
                j += 1
                break
            j += 1
        if not flag:
            continue
        while True:
            if j == n:
                flag = False
                break
            if s[j] == key[2]:
                j += 1
                break
            j += 1
        if flag:
            ans += 1
    print(ans)

main()

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    key = "0" * (3 - len(str(i))) + str(i)
    j = 0
    flag = True
    while True:
        if j == n:
            flag = False
            break
        if s[j] == key[0]:
            j += 1
            break
        j += 1
    if not flag:
        continue
    while True:
        if j == n:
            flag = False
            break
        if s[j] == key[1]:
            j += 1
            break
        j += 1
    if not flag:
        continue
    while True:
        if j == n:
            flag = False
            break
        if s[j] == key[2]:
            j += 1
            break
        j += 1
    if flag:
        ans += 1
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
N = int(input())
ans = [input()]

for i in range(N-1):
    Si = input()
    lef = bisect_left(ans, Si)
    if lef == len(ans):
        ans.append(Si)
    elif ans[lef] != Si:
            ans.insert(lef,Si)

print(len(ans))

### FIXED CODE ###

N = int(input())
ans = set()
for i in range(N):
    Si = input()
    ans.add(Si)
print(len(ans))
### BUGGY CODE ###

s = input()
n = int(input())
isReverse = False
for i in range(n):
    Q = input().split()
    if(Q[0] == '1'):
        isReverse = not isReverse
    else:
        if Q[1] == '1':
            if isReverse: s = s + Q[2]
            else: s = Q[2] + s
        else:
            if isReverse: s = Q[2] + s
            else: s = s + Q[2]
if isReverse:s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
top = ''
n = int(input())
isReverse = False
for i in range(n):
    Q = input().split()
    if(Q[0] == '1'):
        isReverse = not isReverse
    else:
        if Q[1] == '1':
            if isReverse: s += Q[2]
            else: top += Q[2]
        else:
            if isReverse: top += Q[2]
            else: s += Q[2]
if isReverse: s = s[::-1] + top
else: s = top[::-1] + s
print(s)
### BUGGY CODE ###

n = int(input())
boss = list(map(str, input().split()))
exective = set(boss)

for i in range(1, n + 1):
    if str(i) in exective:
        print(boss[i - 1 :].count(str(i)))
    else:
        print(0)

### FIXED CODE ###

n = int(input())
boss = list(map(str, input().split()))
ans = [0] * n
for b in boss:
    ans[int(b) - 1] += 1
for a in ans:
    print(a)
### BUGGY CODE ###

import numpy as np
import itertools

H, W, K = map(int, input().split())
choco = []
for i in range(H):
    choco.append([int(x) for x in list(input())])

arr = np.array(choco)

# W方向にGREEDY
count = H*W

rows = [x for x in range(1,H)]

for k in range(H):

    # H 方向の切込みの組み合わせ
    combs = list(itertools.combinations(rows,k))

    # H 方向に切り込み
    for comb in combs:

        t = [0]
        t.extend(comb)
        t.append(10)
        t.sort()

        # col = [0,1,W]
        left = 0
        ans = []

        noanswer = False

        for right in range(1,W+1):

            # print(right)
            # print(comb)
            # 全 H で成立するか？
            for j in range(len(t)-1):

                if arr[t[j]:t[j+1],left:right].sum() > K:
                    # どこかで K を超えたら、割る

                    if left == right - 1:
                        # 不成立
                        noanswer = True
                        break

                    left = right - 1                
                    ans.append(left)

        if not noanswer:
            tmp = len(ans) + len(comb)
            count = min(count,tmp)

print(count)

### FIXED CODE ###

import numpy as np
import itertools

H, W, K = map(int, input().split())
choco = []
for i in range(H):
    choco.append([int(x) for x in list(input())])

arr = np.array(choco)

# W方向にGREEDY
count = (H-1) + (W-1)


for k in range(H):
    
    # この時点で同じ回数以上切ることが確定なら終了
    if count <= k:
        break

    # H 方向に切り込み
    for comb in itertools.combinations(range(1,H),k):

        # スライスを作っておく
        t = (None,) + comb + (None,)
        s = [slice(t[j],t[j+1],) for j in range(len(t)-1)]
        
        sum_p = [0] * (k+1)
        
        cut = k
        
        for col in zip(*choco):

            # 各ブロック毎の合計を算出
            sum_a = [sum(col[b]) for b in s]
            
            # K を超えるブロックが存在していないか？
            if any(map(K.__lt__, sum_a)):
                # 不成立
                break
            
            # 前まで分割されていないブロックと合わせて、合計を算出
            
            sum_b = [x + y for x,y in zip(sum_p, sum_a)]

            if any(map(K.__lt__, sum_b)):
                cut += 1
                sum_p = sum_a
            else:
                sum_p = sum_b
                
                # 割った位置を記録
        
        else:
            count = min(count,cut)

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

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

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

div = []
for i in range(n):
    div.append(make_divisors(a[i]))


cnt = 0
for j in range(n):
    f = 1
    for k in range(len(div[j])):
        if k != len(div[j])-1:
            if div[j][k] not in a:
                pass
            else:
                f = 0
                break
        else:
            if a.count(div[j][k]) == 1:
                pass
            else:
                f = 0
    if f:
        cnt += 1

print(cnt)

### FIXED CODE ###

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

cnt = [0]*(10**6+1)

for elem in a:
    cnt[elem] += 1

unique = []
for i in range(10**6+1):
    if cnt[i] == 1:
        unique.append(i)

cnt = [0]*(10**6+1)
a = list(set(a))

for elem in a:
    for m in range(elem*2,10**6+1,elem):
        cnt[m] = 1

ans = 0
for elem in unique:
    if cnt[elem] == 0:
        ans += 1

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

N, A, B = map(int, input().split())
ans = 0
while N >= 0:
    ans += min(A,N)
    N -= (A+B)
print(ans)

### FIXED CODE ###

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

X = int(N / (A+B))
Y = int(N % (A+B))

ans += X*A+min(A,Y)

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

import sys 
from math import gcd
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7
N = int(readline())
A = list(map(int,readline().split()))
def lcm(N,a):
    x = a[0]
    for i in range(1, N):
        x = (x * a[i]) // gcd(x, a[i])
    ans = 0 
    for i in range(N):
        ans += x // a[i] % mod
    return ans%mod
ans = lcm(N,A)
print(ans)

### FIXED CODE ###

import sys 
from functools import reduce
from math import gcd
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7
N = int(readline())
A = list(map(int,readline().split()))
lcm = reduce(lambda x,y:x*y//gcd(x,y),A)
ans = 0
ans = sum(lcm//x for x in A)
print(ans%mod)
### BUGGY CODE ###

N = int(input())
s_list = ["".join(sorted(input())) for i in range(N)]

count = 0

s_list = sorted(s_list)

flag = False

for i in range(len(s_list)):
  for j in range(i+1, len(s_list)):
    if s_list[i] == s_list[j]:
      count += 1
      flag = True
    if s_list[i] != s_list[j] and flag == True:
      flag = False
      continue
      
print(count)

### FIXED CODE ###

import collections

N = int(input())
s_list = ["".join(sorted(input())) for i in range(N)]
s_list = sorted(s_list)

count = 0

c = collections.Counter(s_list)

for item in c:
  for pair in range(c[item]):
    count += pair
        
print(count)
### BUGGY CODE ###

import itertools
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(1, N+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

N, M, R = map(int, input().split()) 
rs = list(map(int, input().split()))

inf = 10**9
d = [[inf for i in range(N+1)] for i in range(N+1)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(M):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c
for i in range(1, N+1):
    d[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(d)
ans = inf
for v in itertools.permutations(rs, R):
    dist = 0
    for i in range(R-1):
        dist += d[v[i]][v[i+1]]
    if dist <= ans:
        ans = dist
print(ans)

### FIXED CODE ###

import itertools
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(1, N+1):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

N, M, R = map(int, input().split()) 
rs = list(map(int, input().split()))

inf = 10**9
d = [[inf for i in range(N+1)] for i in range(N+1)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(M):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c
for i in range(1, N+1):
    d[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(d)
ans = inf
for v in itertools.permutations(rs, R):
    dist = 0
    for i in range(R-1):
        dist += d[v[i]][v[i+1]]
    if dist <= ans:
        ans = dist
print(ans)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

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

for _ in range(K):
    B = [0 for _ in range(N)]
    end = True

    for i in range(N):
        left = max(0, i - A[i])
        right = min(N - 1, i + A[i])

        B[left] += 1
        if right + 1 < N:
            B[right + 1] -= 1

    for i in range(N):
        if i > 0:
            B[i] += B[i - 1]
        if B[i] != N:
            end = False

    A = B

    if end:
        break

for a in A:
    print(a, end=" ")

print()


### FIXED CODE ###

from sys import stdin
input = stdin.readline

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

for _ in range(K):
    B = [0 for _ in range(N)]
    end = True

    for i in range(N):
        left = max(0, i - A[i])
        right = min(N - 1, i + A[i])

        B[left] += 1
        if right + 1 < N:
            B[right + 1] -= 1

    for i in range(N):
        if i > 0:
            B[i] += B[i - 1]
        if B[i] != N:
            end = False

    A = B

    if end:
        break

for a in A:
    print(a, end=" ")

print()
### BUGGY CODE ###

def fx(n):
  cnt = 0

  for i in range(1,10000):
    if (i+1+1)**2 - i*1 - 1*1 - 1*i > n: break
    for j in range(1, 10000):
      if (1+j+1)**2 - 1*j - j*1 - 1*1 > n : break
      for k in range(1, 10000):
        if (1+1+k)**2 - 1*1 - 1*k - k*1 > n: break
        formula = (i+j+k)**2 - i*j - j*k - k*i
        if formula == n:
          cnt+=1
        if formula >= n:
          break
  
  return cnt


n = int(input())
for i in range(1,n+1):
  print(fx(i))



### FIXED CODE ###

def fx(n):
  s = [0]*(n+1)
  for i in range(1,10000):
    if (i+1+1)**2 - i*1 - 1*1 - 1*i > n: break
    for j in range(1, 10000):
      if (1+j+1)**2 - 1*j - j*1 - 1*1 > n : break
      for k in range(1, 10000):
        if (1+1+k)**2 - 1*1 - 1*k - k*1 > n: break
        formula = (i+j+k)**2 - i*j - j*k - k*i
        if formula <= n and formula > 0:
          s[formula] += 1
        if formula >= n:
          break
  return s


n = int(input())
s = fx(n)
for i in range(1,n+1):
  print(s[i])
### BUGGY CODE ###

s = input()
q = int(input())
t = 1
f = 1
for i in range(q):
    que = input().split()
    if que[0] == "1":
        t *=-1
    else:
        if que[1] == "1":
            f = 1
        else:
            f = -1
        if t*f == 1:
            s = que[2] + s
        else:
            s = s + que[2]

if t == -1:
    s = s[::-1]

print(s)


### FIXED CODE ###

s = input()
q = int(input())
t = 0
f = -1
x = ["",""]
for i in range(q):
    que = input().split()
    if que[0] == "1":
        t += 1
    else:
        x[(int(que[1])-1+t)%2] += que[2]

s = x[0][::-1] + s + x[1]
if t%2 == 1:
    s = s[::-1]

print(s)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(max(a)+1):
  x=0
  for ai in a:
    if ai==i or ai-1==i or ai+1==i:
      x+=1
  ans=max(ans,x)
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
an = [0]*(max(a)+2)
for i in a:
  if i!=0:
    an[i-1]+=1
  an[i+1]+=1
  an[i]+=1
print(max(an))
### BUGGY CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) # xで死ぬ
  heappush(q,(t-x,0,x)) # xで死ななくなる

for i in range(Q):
  d = int(input())
  heappush(q,(d,2,i))
answer = [-1]*Q

se = []
remove_task = []

while q:
  a,c,b = heappop(q)
  if not c:
    if b == se[0]:
      heappop(se)
      while remove_task:
        x = se[0]
        y = remove_task[0]
        if x == y:
          heappop(se)
          heappop(remove_task)
          continue
        break
    else:
      heappush(remove_task,b)
  elif c&1:
    heappush(se,b)
  else:
    if se:
      answer[b] = se[0]
  #print(a,c,b,se,remove_task)
print('\n'.join(map(str,answer)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  q.append((s-x,1,x)) # xで死ぬ
  q.append((t-x,0,x)) # xで死ななくなる

for i in range(Q):
  d = int(input())
  q.append((d,2,i))
answer = [-1]*Q

se = set() # 引っかかってる場所

q.sort()

min_se = 10**18
flag = False # min_seが正しい

for a,c,b in q:
  if not c:
    se.remove(b)
    if min_se == b:
      flag = False
  elif c&1:
    se.add(b)
    if b < min_se:
      min_se = b
      flag = True
  else:
    if se:
      if not flag:
        min_se = min(se)
        flag = True
      answer[b] = min_se

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

#Pythonだと少し間に合わない
N = int(input())

for h in range(3500, 0, -1):
    for n in range(3500, 0, -1):
        if (N * h * n) >= (4 * h * n - N * (h + n)) > 0:
            if (N * h * n) % (4 * h * n - N * (h + n)) == 0:
                w = (N * h * n) // (4 * h * n - N * (h + n))
                print (h, n, w)
                exit()


### FIXED CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        if (N * h * n) >= (4 * h * n - N * (h + n)) > 0:
            if (N * h * n) % (4 * h * n - N * (h + n)) == 0:
                w = (N * h * n) // (4 * h * n - N * (h + n))
                print (h, n, w)
                exit()
### BUGGY CODE ###

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

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friends[a].add(b)
    friends[b].add(a)

flg = [0]*n
max_ans = 0

for i in range(n):
    if flg[i]:
        continue
    for j in range(i+1, n):
        if not friends[i].isdisjoint(friends[j]):
            friends[i] |= friends[j]
            flg[j] = 1
    ans = len(friends[i])
    max_ans = max(max_ans, ans)

print(max_ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

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


def dfs(i):
    ans[-1] += 1
    flg[i] = 1
    for j in friends[i]:
        if not flg[j]:
            dfs(j)
    return


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friends[a].append(b)
    friends[b].append(a)

flg = [0]*n
ans = []

for i in range(n):
    ans.append(0)
    if not flg[i]:
        dfs(i)

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

N = int(input())
S = list(input())
count = 0

for i in range(N):
    pre_reader = S[:i]
    post_reader = S[i+1:]
    pre_count = len([k for k in range(i) if S[k] == 'W'])
    post_count = len([k for k in range(i+1, N) if S[k] == 'E'])
    if (count > pre_count + post_count) and (i >= 1):
        count = pre_count + post_count
    elif i == 0:
        count = pre_count + post_count

print(count)

### FIXED CODE ###

N = int(input())
S = list(input())

pre_count = 0
post_count = len([k for k in range(1, N) if S[k] == 'E'])
count = post_count
for i in range(1, N):
    if S[i-1] == 'W':
        pre_count += 1
    if S[i] == 'E':
        post_count -= 1
    if count > pre_count + post_count:
        count = pre_count + post_count

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

def func(N,A):
  result = 0
  for i in range(0,N-1,1):
    for j in range(i+1,N,1):
      result += (A[i] * A[j])
  return result % (10 ** 9 + 7)

if __name__ == "__main__":
  N = int(input())
  A = list(map(int, input().split()))
  print(func(N,A))

### FIXED CODE ###

MOD = 10 ** 9 + 7

def func(N,A):
  result = 0
  S = sum(A) % MOD
  for x in A:
    S -= x
    S %= MOD
    result += x * S
    result %= MOD
  result %= MOD
  return result

if __name__ == "__main__":
  N = int(input())
  A = list(map(int, input().split()))
  print(func(N,A))
### BUGGY CODE ###

from numpy import array
n,k,q = map(int,input().split())
s = array([k]*n)
str = array([-1]*n)
for i in range(q):
  s+=str
  num = int(input())
  s[num-1]+=1  
for j in s:
  if j<=0:
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

from numpy import array
n,k,q = map(int,input().split())
s = array([k-q]*n)
for i in range(q):
  num = int(input())
  s[num-1]+=1  
for j in s:
  if j<=0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

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

while(len(A)!=0):
  buf=[A[0]]
  A.pop(0)
  buf2=list(set(A) & set(buf))
  if len(buf2)!=0:
    print("NO")
    exit(0)
  
print("YES")

### FIXED CODE ###

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

A=sorted(A)

for i in range(0,N):
  if len(A) > i+1:
    if A[i] == A[i+1]:
      print("NO")
      exit(0)
print("YES")
### BUGGY CODE ###


N = int(input())
L = list(map(int, input().split()))
# L = sorted(L)
L = sorted(L, reverse=True)

x = 0


for i in range(len(L)):   
    for j in range(i+1, len(L)):
        if L[i] < L[j] * 2:
            l = L[i] - L[j]
            for k in range(j+1, len(L)):
                if L[k] > l:
                    x += 1
                else:
                    break
        else:
            break
print(x)
                

### FIXED CODE ###

import bisect

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

cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        up = l[j] + l[i]
        #l[k] = up となるようなkのうち最小のものを見つけろ
        k = bisect.bisect_left(l, up)
        cnt += k - j - 1
print(cnt)