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

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

l = [[] for j in range(n)]

for i in range(m):
    x,y = map(int, input().split())
    l[x-1].append(y-1)
    l[y-1].append(x-1)

connect = []
a = []
v = []

for i in range(n):
    if i not in v:
        connect.append([i])
        a.append([p[i]-1])
        v.append(i)
        stack =[i]
        visited = [i]
        while stack:
            q = stack.pop()
            for j in range(len(l[q])):
                if l[q][j] not in visited:
                    connect[-1].append(l[q][j])
                    a[-1].append(p[l[q][j]]-1)
                    visited.append(l[q][j])
                    stack.append(l[q][j])
                    v.append(l[q][j])

ans = 0

for i in range(len(connect)):
    ans += len(set(a[i]) & set(connect[i]))

print(ans)


### FIXED CODE ###

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

l = [[] for j in range(n)]

for i in range(m):
    x,y = map(int, input().split())
    l[x-1].append(y-1)
    l[y-1].append(x-1)

connect = []
a = []
v = [0 for i in range(n)]

for i in range(n):
    if v[i] == 0:
        connect.append([i])
        a.append([p[i]-1])
        v[i]=1
        stack =[i]
        while stack:
            q = stack.pop()
            for j in range(len(l[q])):
                if v[l[q][j]]==0:
                    connect[-1].append(l[q][j])
                    a[-1].append(p[l[q][j]]-1)
                    stack.append(l[q][j])
                    v[l[q][j]]=1

ans = 0

for i in range(len(connect)):
    ans += len(set(a[i]) & set(connect[i]))

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

n=int(input())
s=input()
keys=set()
keys.add(s[0:3])
for i in range(3,n):
	adkeys=set()
	for key in keys:
		adkeys.add(key[0]+key[1]+s[i])
		adkeys.add(key[0]+key[2]+s[i])
		adkeys.add(key[1]+key[2]+s[i])
	keys=keys|adkeys
print(len(keys))

### FIXED CODE ###

n=int(input())
s=input()
numbers=[str(i).zfill(3) for i in range(1000)]

count=0
for num in numbers:
	j=0
	for i in range(n):
		if num[j]==s[i]:
			j+=1
		if j==3:
			break
	if j==3:
		count+=1
print(count)
### BUGGY CODE ###

L,R=map(int,input().split())
li=[]
for i in range(L,R):
  for j in range(i+1,R+1):
    mod=(i*j)%2019
    li.append(mod)
print(min(li))

### FIXED CODE ###

L,R=map(int,input().split())
R=min(R, L+2019)
li=[]
for i in range(L,R):
  for j in range(i+1,R+1):
      mod=(i*j)%2019
      li.append(mod)
      if mod==0:
        break
print(min(li))
### BUGGY CODE ###

import collections
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

m = int(input())
a = list(map(int,input().split()))[:m]

memo = {}

for i in a:
    res = 0
    t = a[:]
    t.remove(i)
    c = collections.Counter(t)
    for v in c.values():
        if v >= 2:
            if not memo.get(v):
                memo[v] = combinations_count(v, 2)

            res += memo[v]
    print(res)

### FIXED CODE ###

import collections


m = int(input())
A = list(map(int,input().split()))[:m]
c = collections.Counter(A)
 
def hoge(n):
    return n * (n - 1) // 2

full = sum([ hoge(i) for i in c.values()])

for a in A:
    print(full - hoge(c[a]) + hoge(c[a]-1))
### BUGGY CODE ###

SIZE=10**5+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD
 
def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
 
def chofuku(ball,box): # nHk mod MOD の計算
    return choose(box+ball-1,box)


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

ans=0
for i in range(N):
    for j in range(i+K-1,N):
        ans+=(A[j]-A[i])*choose(j-i-1,K-2)
        ans%=MOD

print(ans)



### FIXED CODE ###

SIZE=10**5+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD
 
def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
 
def chofuku(ball,box): # nHk mod MOD の計算
    return choose(box+ball-1,box)


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

smax=0
smin=0
for i in range(N):
    smax+=A[i]*choose(i,K-1)
    smax%=MOD
    smin+=A[i]*choose(N-i-1,K-1)
    smin%=MOD

print((smax-smin)%MOD)
### BUGGY CODE ###

N,Q = map(int,input().split())
s = str(input())

for _ in range(Q):
    l,r = map(int,input().split())
    print(s[l-1:r].count("AC"))

### FIXED CODE ###

N,Q = map(int,input().split())
s = input()
t = [0]
ans = []
for i in range(N):
    if s[i:i+2] == "AC":
        t.append(t[i] + 1)
    else:
        t.append(t[i])
for i in range(Q):
    l,r = map(int,input().split())
    ans.append(t[r-1]-t[l-1])
for i in ans:
    print(i)
### BUGGY CODE ###

from collections import deque
n,x,y = map(int,input().split())
cnt = [0]*(n)
path = [(i, i+1) for i in range(n-1)]
path.append((x-1, y-1))
res = []
for i in range(n):
    d = [float('inf')]*n
    que = deque([(i, 0)])
    while que:
        idx, c = que.popleft()
        if d[idx]!=float('inf'):
            continue
        else:
            d[idx] = min(d[idx], c)
            for s,g in path:
                if s==idx:
                    que.append((g, c+1))
                if g==idx:
                    que.append((s, c+1))
    res.append(d)

for r in res:
    for i in range(n-1):
        cnt[i] += r.count(i)
for c in cnt[1:]:
    print(c//2)

### FIXED CODE ###

from collections import deque
n,x,y = map(int,input().split())
x,y = x-1 ,y-1
g = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    que = deque([(i, 0)])
    while que:
        node, cost = que.popleft()
        if g[i][node]!=float('inf'):
            continue
        else:
            g[i][node] = cost
            if node>0:
                que.append((node-1, cost+1))
            if node<n-1:
                que.append((node+1, cost+1))
            if node==x:
                que.append((y, cost+1))
            if node==y:
                que.append((x, cost+1))
cnt = [0]*n
for i in range(n):
    for j in range(i+1, n):
        cnt[g[i][j]] += 1
for c in cnt[1:]:
    print(c)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
import heapq

n = int(input())
rev_g = [[] for _ in range(n+1)]
for i in range(n-1):
    a = int(input())
    rev_g[a].append(i+2)

def f(v):
    m = len(rev_g[v])
    if m == 0:
        return 0
    q = []
    for nv in rev_g[v]:
        heapq.heappush(q, f(nv))
    q.sort()
    dp = [0] * (m+1)
    for i in range(m):
        dp[i+1] = max(q[i]+1, dp[i]+1)
    return dp[m]


print(f(1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n = int(input())
rev_g = [[] for _ in range(n+1)]
for i in range(n-1):
    a = int(input())
    rev_g[a].append(i+2)

def f(v):
    m = len(rev_g[v])
    if m == 0:
        return 0
    q = []
    for nv in rev_g[v]:
        q.append(f(nv))
    q.sort()
    dp = [0] * (m+1)
    for i in range(m):
        dp[i+1] = max(q[i]+1, dp[i]+1)
    return dp[m]


print(f(1))
### BUGGY CODE ###

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

h = [0] * H
w = [0] * W

hw = []

for _ in range(H):
    hw.append([0] * W)

for _ in range(M):
    a,b = list(map(int,input().split()))
    h[a - 1] += 1
    w[b - 1] += 1
    hw[a - 1][b - 1] += 1
    
hm = max(h)
wm = max(w)

hp = [i for i, v in enumerate(h) if v == hm]
wp = [i for i, v in enumerate(w) if v == wm]

for x in hp:
    for y in wp:
        if hw[x][y] == 0:
            print(hm + wm)
            exit()
else:
    print(hm + wm - 1)



### FIXED CODE ###


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

h = [0] * H
w = [0] * W

hw = {}

for _ in range(M):
    a, b = list(map(int, input().split()))
    h[a - 1] += 1
    w[b - 1] += 1
    temp = "x" + str(a - 1) + "y" + str(b - 1)
    hw[temp] = 1

hm = max(h)
wm = max(w)

hp = [i for i, v in enumerate(h) if v == hm]
wp = [i for i, v in enumerate(w) if v == wm]

for x in hp:
    for y in wp:
        temp = "x" + str(x) + "y" + str(y)
        if temp not in hw:
            print(hm + wm)
            exit()
else:
    print(hm + wm - 1)
### BUGGY CODE ###

N,M = map(int,input().split())
for i in range(M):
    l,r = map(int,input().split())
    if i == 0:
        set_a = set(list(range(l,r+1)))
    set_b = set(list(range(l,r+1)))
    set_a = set_a & set_b
print(len(set_a))

### FIXED CODE ###

N,M = map(int,input().split())
lst_l=[]
lst_r=[]
for i in range(M):
    l,r = map(int,input().split())
    lst_l.append(l)
    lst_r.append(r)
ans = min(lst_r)-max(lst_l)+1
if ans >=0:print(ans)
else:print(0)
### BUGGY CODE ###

n = int(input())
s = input()

pass_set = set([])
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            pass_set.add(s[i] + s[j] + s[k])

print(len(pass_set))


### FIXED CODE ###

n = int(input())
s = input()

candidates = [0 for i in range(10 ** 3)]

count = 0
for i in range(1000):
    tmp_pass = '{:03}'.format(i)

    index_0 = s.find(tmp_pass[0])
    if index_0 != -1 and index_0 < len(s) - 2:
        s_1 = s[index_0 + 1:]
        index_1 = s_1.find(tmp_pass[1])
        if index_1 != -1 and index_1 < len(s_1) - 1:
            s_2 = s_1[index_1 + 1:]
            # print(tmp_pass)
            # print(s_2)
            # index_2 = s_2.find(tmp_pass[2])
            # print(index_2)
            if s_2.find(tmp_pass[2]) != -1:
                count += 1

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

from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  updates = []
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw not in t or nv > t[nw]:
      for u in updates:
        if nw <= u[0] and nv <= u[1]:
          continue
      updates.append([nw, nv])
  for key in list(t.keys()):
    for u in updates:
        if key <= u[0] and t[key] <= u[1]:
          del t[key]
          break
  for u in updates:
    t[u[0]] = u[1]
print(max(t.values()))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

import bisect
import itertools

def binary_search(left, right, search, List):
    while right-left > 1:
        mid = (left+right)//2
        if List[mid] == search:
            return mid
        else:
            if search > List[mid]:
                left = mid
            else:
                right = mid
    return -1


n = int(input())
s = input()

d = {"R": [], "G": [], "B": []}

for i in range(n):
    d[s[i]].append(i)

p=list(itertools.permutations(["R","G","B"]))

ans = 0
for a,b,c in p:
    for r in range(len(d[a])):
        second = bisect.bisect_left(d[b], d[a][r])
        for g in range(second, len(d[b])):
            third = bisect.bisect_left(d[c], d[b][g])
            ans += len(d[c])-third
            if binary_search(-1,len(d[c]),2*d[b][g]-d[a][r],d[c])!=-1:
                ans-=1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
r=0
g=0
b=0
for i in range(n):
    if s[i]=="R":
        r+=1
    elif s[i]=="B":
        b+=1
    else:
        g+=1
ans=r*b*g

for i in range(n):
    for g in range(i+1,n):
        if s[i]!=s[g] and 2*g-i<n:
            if s[2*g-i]!=s[i] and s[2*g-i]!=s[g]:
                ans-=1

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


def solve(K, S):
    count = 0
    for x in range(K+1):
        for y in range(K+1):
            for z in range(K+1):
                if(x+y+z == S):count+=1
    return count

def main():
    K, S = map(int, input().split())
    print(solve(K, S))

main()

### FIXED CODE ###


def solve(K, S):
    import bisect
    count = 0
    z_array = [i for i in range(K+1)]
    for x in range(K+1):
        for y in range(K+1):
                z = S - x - y
                if(z >= 0 and z <= K):count+=1
    return count

def main():
    K, S = map(int, input().split())
    print(solve(K, S))
#print(solve(2, 2))
#print(solve(5, 15))
main()
### BUGGY CODE ###

import sys
H,W,m = map(int,input().split())
h_ls = [0] * H
w_ls = [0] * W
bombers = [[0,0] for _ in range(m)]
for i in range(m):
    h,w = map(int,input().split())
    h_ls[h-1] += 1
    w_ls[w-1] += 1
    bombers[i] = [h-1,w-1]
h_max = max(h_ls)
h_max_args = [-1] * H
for i in range(H):
    if h_ls[i] == h_max:
        h_max_args[i] = i

w_max = max(w_ls)
w_max_args = [-1] * W
for i in range(W):
    if w_ls[i] == w_max:
        w_max_args[i] = i

for h in h_max_args:
    for w in w_max_args:
        if h == -1 or w == -1:
            continue
        if not [h,w] in bombers:
            print(w_max+h_max)
            sys.exit()

print(w_max+h_max-1)

### FIXED CODE ###

import sys
from collections import Counter
H,W,m = map(int,input().split())
h_ls = [0] * H
w_ls = [0] * W
bombers = [(0,0) for _ in range(m)]
for i in range(m):
    h,w = map(int,input().split())
    h_ls[h-1] += 1
    w_ls[w-1] += 1
    bombers[i] = (h-1,w-1)

h_max = max(h_ls)
h_counter = Counter(h_ls)
# Couter使ってみる
h_max_args = [0]*h_counter[h_max]
next_ind = 0
for i in range(H):
    if h_ls[i] == h_max:
        h_max_args[next_ind] = i
        next_ind += 1

w_max = max(w_ls)
w_counter = Counter(w_ls)
w_max_args = [0]*w_counter[w_max]
next_ind = 0
for i in range(W):
    if w_ls[i] == w_max:
        w_max_args[next_ind] = i
        next_ind += 1

bombers = set(bombers)
for h in h_max_args:
    for w in w_max_args:
        if not (h,w) in bombers:
            print(w_max+h_max)
            sys.exit()

print(w_max+h_max-1)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [float("inf") for i in range(n)]
dp[0] = 0
for i in range(1,n):
    if(i<k):
        for j in range(1,i+1):
            if(dp[i] > dp[i-j]+abs(h[i]-h[i-j])):
                dp[i] = dp[i-j]+abs(h[i]-h[i-j])
    else:
        for j in range(1,k+1):
            if(dp[i] > dp[i-j]+abs(h[i]-h[i-j])):
                dp[i] = dp[i-j]+abs(h[i]-h[i-j])
print(dp[-1])


### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [float("inf") for i in range(n)]
dp[0] = 0
for i in range(1,n):
    if(i<k):
        for j in range(1,i+1):
            if(dp[i] > dp[i-j]+abs(h[i]-h[i-j])):
                dp[i] = dp[i-j]+abs(h[i]-h[i-j])
    else:
        for j in range(1,k+1):
            if(dp[i] > dp[i-j]+abs(h[i]-h[i-j])):
                dp[i] = dp[i-j]+abs(h[i]-h[i-j])
print(dp[-1])
### BUGGY CODE ###

N = int(input())
num = input().rstrip().split(" ")
Ai = []
M =[]


def gcd_list(numbers):
  def gcd(a,b):
    while b!=0:
      a,b=b,a%b
    return a
  
  ans = numbers[0]
  for i in range(1, N-1):
    ans = gcd(ans, numbers[i])
  return ans

for i in range(N):
  Ai.append(int(num[i]))
for i in range(N):
  a = Ai.pop(i)
  M.append(gcd_list(Ai))
  Ai.insert(i,a)

print(max(M))


### FIXED CODE ###

from fractions import gcd
 
n = int(input())
a = list(map(int, input().split()))
 
rs, ls = [0], [0]
for i in range(n-1):
  rs.append(gcd(rs[i], a[i]))
  ls.append(gcd(ls[i], a[-i-1]))
 
print(max(gcd(r, l) for r, l in zip(rs, ls[::-1])))
### BUGGY CODE ###

n=int(input())
s=list(input())
q=int(input())
c=[chr(i) for i in range(97, 97+26)]
l=[input().split() for i in range(q)]
L=[]
for i in range(q):
  if l[i][0]=='2':
    L.append([int(l[i][1]),int(l[i][2])])

a=[[0 for i in range(n)] for i in range(26)]
b=[]
for i in range(n):
  a[c.index(s[i])][i]=1
for i in range(26):
  x=[0]
  for j in range(n):
    x.append(x[-1]+a[i][j])
  b.append(x)

L2=[[0 for i in range(26)] for i in range(len(L))]
for i in range(len(L)):
  for j in range(26):
    L2[i][j]=b[j][L[i][1]]-b[j][L[i][0]-1]

j2=0
for i in range(q):
  if l[i][0]=='1':
    for j in range(len(L)):
      if L[j][0]<=int(l[i][1])<=L[j][1]:
        L2[j][c.index(l[i][2])]+=1
        L2[j][c.index(s[int(l[i][1])-1])]-=1
    s[int(l[i][1])-1]=l[i][2]
  else:
    ans=0
    for i in range(26):
      if L2[j2][i]!=0:
        ans+=1
    print(ans)
    j2+=1

### FIXED CODE ###

n=int(input())
s=list(input())
q=int(input())
c=[chr(i) for i in range(97, 97+26)]
l=[input().split() for i in range(q)]

def segfunc(x,y):
  return x+y

def init(init_val,c):
  for i in range(n):
    seg[c][i+num-1]=init_val[i]
  for i in range(num-2,-1,-1):
    seg[c][i]=segfunc(seg[c][2*i+1],seg[c][2*i+2])

def update(k,x,c):
  k+=num-1
  seg[c][k]+=x
  while k:
    k=(k-1)//2
    seg[c][k]=segfunc(seg[c][k*2+1],seg[c][k*2+2])

def query(p,q,c):
  if q<=p:
    return ide_ele
  p+=num-1
  q+=num-2
  res=ide_ele
  while q-p>1:
    if p&1==0:
      res=segfunc(res,seg[c][p])
    if q&1==1:
      res=segfunc(res,seg[c][q])
      q-=1
    p=p//2
    q=(q-1)//2
  if p==q:
    res=segfunc(res,seg[c][p])
  else:
    res=segfunc(segfunc(res,seg[c][p]),seg[c][q])
  return res

ide_ele=0

num=2**(n-1).bit_length()
seg=[[ide_ele]*2*num for i in range(26)]

L=[[0 for i in range(n)] for j in range(26)]
for i in range(n):
  L[c.index(s[i])][i]+=1

for i in range(26):
  init(L[i],i)

for i in range(q):
  if l[i][0]=='1':
    update(int(l[i][1])-1,1,c.index(l[i][2]))
    update(int(l[i][1])-1,-1,c.index(s[int(l[i][1])-1]))
    s[int(l[i][1])-1]=l[i][2]
  else:
    ct=0
    for j in range(26):
      if query(int(l[i][1])-1,int(l[i][2]),j)!=0:
        ct+=1
    print(ct)
### BUGGY CODE ###

n=int(input());a=list(map(int,input().split()));b,c=sum(a),float('inf')
for i in range(1,n):
  c=min(c,abs(b-2*sum(a[:i])))
print(c)

### FIXED CODE ###

n=int(input());a=list(map(int,input().split()));f,b,c=0,sum(a),float('inf')
for i in range(n-1):
  f,b=f+a[i],b-a[i]
  c=min(c,abs(f-b))
print(c)
### BUGGY CODE ###

from collections import deque

K = int(input())

list = [1,2,3,4,5,6,7,8,9]
i = 0
for i in range(K):
    v = list.pop(0)

    t = v%10

    if t != 0:
        list.append(10*v + (t-1))

    list.append(10*v + t)

    if t != 9:
        list.append(10*v + (t+1))


print(v)


### FIXED CODE ###

from collections import deque

K = int(input())

list = deque(range(1,10))
i = 0
for i in range(K):
    v = list.popleft()

    t = v%10

    if t != 0:
        list.append(10*v + (t-1))

    list.append(10*v + t)

    if t != 9:
        list.append(10*v + (t+1))


print(v)
### BUGGY CODE ###

n, k = map(int, input().split())
a = [int(i) for i in input().split()]
s = [0 for i in range(n)]
p = [0 for i in range(n)]

s[0] = a[0]
for i in range(1, n):
  s[i] = s[i-1] * a[i]

p[k-1] = s[k-1]
for i in range(k, n):
  p[i] = int(s[i] / s[i-k])

for i in range(k, n):
  if p[i] > p[i-1]:
    print("Yes")
  else:
    print("No")
    

### FIXED CODE ###

n, k = map(int, input().split())
a = [int(i) for i in input().split()]
res = 0
for i in range(n-k):
  if a[i+k] - a[i] > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

n = int(input())
ar = [[-1 for i in range(n)] for j in range(n)]
ar2 = [[] for i in range(n)]
for i in range(n-1):
    ipt = list(map(int,input().split()))
    ar[ipt[0]-1][ipt[1]-1] = ipt[2]%2
    ar[ipt[1]-1][ipt[0]-1] = ipt[2]%2
    ar2[ipt[0]-1].append(ipt[1]-1)
    ar2[ipt[1]-1].append(ipt[0]-1)

ans = [[] for i in range(n)]
u = 0
ans[u] = 0
queue = [u] #キュー
check = [u] #訪問済み

while True:
    if len(queue) == 0:
        break
    u = queue[0]
    queue.pop(0)
    for v in ar2[u]:
        if not v in check:
            check.append(v)
            ans[v] = (ans[u] + ar[u][v])%2
            queue.append(v)

for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

n = int(input())
ar = [[] for i in range(n)]
for i in range(n-1):
    ipt = list(map(int,input().split()))
    ar[ipt[0]-1].append((ipt[1]-1,ipt[2]))
    ar[ipt[1]-1].append((ipt[0]-1,ipt[2]))

ans = [-1 for i in range(n)]
u = 0
ans[u] = 0
queue = [u] #キュー
l = 1
while True:
    if l == 0:
        break
    u = queue.pop(0)
    l -= 1
    for v in ar[u]:
        if ans[v[0]] < 0:
            ans[v[0]] = ans[u] + v[1]
            queue.append(v[0])
            l+=1

for i in range(n):
    print(ans[i]%2)
### BUGGY CODE ###

# cook your dish here
import numpy as np
n,m,q = map(int,input().split())
lr = []
for i in range(m):
    l = list(map(int,input().split()))	
    lr.append(l)
 
ass = np.zeros((n,n))
        
        
for i in range(m):
    ass[lr[i][0]-1][lr[i][1]-1] += 1
        
#print(ass)
 
for i in range(q):
    p,qa = map(int,input().split())
    ans = 0
    for i in range(p-1,qa):
        ans += sum(ass[i][:qa:])
    print(int(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m,q = map(int,input().split())

res = [[0]*n for i in range(n)]
for i in range(m):
    L,r = map(int,input().split())
    L -= 1
    r -= 1
    res[r][0] += 1
    if L != n-1:
        res[r][L+1] -= 1

for i in range(n):
    for j in range(1,n):
        res[i][j] += res[i][j-1]
for i in range(n):
    for j in range(1,n):
        res[j][i] += res[j-1][i]
for i in range(q):
    p,q = map(int,input().split())
    print(res[q-1][p-1])
### BUGGY CODE ###

n=int(input())
blist=[int(input()) for a in range(n)]
vlist=[1]
while True:
    if 2 in vlist:
        print(len(vlist)-1)
        break
    vlist.append(blist[vlist[-1]-1])
    if vlist[-1] in vlist[0:-1]:
        print(-1)
        break

### FIXED CODE ###

from collections import deque
n=int(input())
blist=deque([int(input()) for a in range(n)])
vlist=1
count=0
while True:
    if count>n:
        print(-1)
        break
    if 2 == vlist:
        print(count)
        break
    vlist=blist[vlist-1]
    count+=1
### BUGGY CODE ###

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

res = 0

for i in range(N-2):
    L1 = L[i+1:]
    a = L[i]
    for j in range(len(L1)-1):
        L2 = L1[j+1:]
        b = L1[j]
        temp1 = max(L2)
        temp2 = min(L2)
        if temp2 >= a + b:
            break
        elif temp1 <= a - b:
            break
        elif temp1 <= b - a:
            break
        for k in range(len(L2)):
            c = L2[k]
            sum = a + b + c
            if (sum > 2*a) & (sum > 2*b) & (sum > 2*c):
                res += 1

print(res)


### FIXED CODE ###

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

v = L[:]
v.sort()

res = 0

import bisect

for i in range(N-2):
    a = v[i]
    for j in range(i+1,N-1):
        b = v[j]
        sup = a + b
        #inf = max(a-b,b-a)
        iterS = bisect.bisect_left(v,sup)
        #iterI = bisect.bisect_left(v,inf+1)
        #print(a,b,sup,inf,iterS,iterI)
        res += iterS - (j+1)

print(res)