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

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

D = [0]
for i in range(N):
    D.append(A[i]+D[i])
ans = 0
for i in range(N):
    a = i+A[i]
    S = D[N]-D[i+1]
    for absij in range(1,N-a):
        j = a+absij
        if absij>S:break
        if A[i]+A[j]==j-i:
            ans+=1
        S-=A[j]
print(ans)

### FIXED CODE ###

from collections import Counter

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

L = [A[i]+i for i in range(N)]
R = [j-A[j] for j in range(N)]

l = Counter(L)
r = Counter(R)

ans = 0
for i in l.keys():
    ans += l[i]*r[i]

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

import collections


def p_c():
    n = int(input())
    ans = 0

    l = []

    for _ in range(n):
        s = collections.Counter(input())
        for le in l:
            if le == s:
                ans += 1

        l.append(s)

    print(ans)


if __name__ == '__main__':
    p_c()

### FIXED CODE ###

from collections import Counter

def p_c():
    n = int(input())
    ans = 0

    l = ["".join(sorted(input())) for _ in range(n)]

    a = Counter(l).values()

    for i in a:
        ans += sum(range(i))

    print(ans)
    
    
if __name__ == '__main__':
    p_c()
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().split()]
for i in range(n-1):
  a[i+1]*=a[i]
  
if a[n-1]>10**18:
  print("-1")
else:
  print(a[n-1])

### FIXED CODE ###

import math
n=int(input())
a=[int(x) for x in input().split()]
a_log=[]
if 0 not in a:
  for i in a:
    i_log=math.log10(i)
    a_log.append(i_log)
  
  if sum(a_log)>18:
    print("-1")
  else:
    for i in range(n-1):
  	  a[i+1]*=a[i]
    if a[n-1]>10**18:
      print("-1")
    else:
      print(a[n-1])
else:
  print("0")
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
 
for x in range(N // R + 1):
    Rx = R * x
    for y in range(N // G + 1):
        check = N - Rx - G * y
        if check % B == 0 and 0 <= check // B <= N // B:
            ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
 
for Rx in range(0, N+1, R):
    for Gy in range(0, N+1, G):
        check = N - Rx - Gy
        if check % B == 0 and 0 <= check // B <= N // B:
            ans += 1
print(ans)
### BUGGY CODE ###

# coding: utf-8
N = int(input())
A = list(map(int, input().split()))
A.reverse()
B = [0 for i in range(N)]
for i in range(N):
    tmp = 0
    for j in range(i):
        tmp += B[j]
    if A[i] % 2 != tmp % 2:
        B[i] = 1
B.reverse()
ans = []
M = sum(B)
for i in range(N):
    if B[i] == 1:
        ans.append(i+1)
print(M)
print(*ans)

### FIXED CODE ###

#coding: utf-8
N = int(input())
A = [0] + list(map(int, input().split()))
B = [0 for _ in range(N+1)]
ans = []
for i in range(N, 0, -1):
    v = 0
    j = i
    while j <= N:
        v += B[j]
        j += i
    if A[i] != v % 2:
        ans.append(i)
        B[i] = 1

ans.sort()
print(len(ans))
if len(ans) != 0:
    print(*ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
L = list(input())
for i in range(n):
    if L[i] == "W":
        L[i] = 0
    else:
        L[i] = 1

ans = 3*(10**5)
for i in range(1,n-1):
    Ll = np.array(L[:i])
    Lr = np.array(L[i+1:])
    Ll = np.cumsum(Ll)
    Lr = np.cumsum(Lr)
    if L[i] == 0:
        ans = min(ans,Ll[-1]+Lr[-1])
    elif L[i] == 1:
        ans = min(ans,len(Ll)-Ll[-1]+len(Lr)-Lr[-1])
    ans = min(ans,len(Ll)-Ll[-1]+Lr[-1])
print(ans)

### FIXED CODE ###

from itertools import accumulate
n = int(input())
L = list(input())

R = L.count("E")

for i in range(n):
    if L[i] == "W":
        L[i] = 1
    elif L[i] == "E":
        L[i] = 0
liw = list(accumulate(L))

for i in range(n):
    if L[i] == 0:
        L[i] = 1
    elif L[i] == 1:
        L[i] = 0

lie = list(accumulate(L))

for i in range(n):
    lie[i] = R-lie[i]

ans = 10**10
for i in range(n):
    west_num = liw[i]
    east_num = lie[i]
    #print(west_num,east_num,L[i])
    if L[i] == 0:
        west_num =max(west_num -1,0)

    ans = min(ans,west_num+east_num)
print(ans)
### BUGGY CODE ###

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

MOD = 998244353

interval = []
for i in range(K):
    L,R = map(int,input().split())
    for j in range(L,R+1):
        interval.append(j)

dp = [0]*N
dp[0] = 1

for i in range(N-1):
    for j in interval:
        if j <= N-1 - i:
            dp[i+j] += dp[i]
            dp[i+j] %= MOD

print(dp[N-1])

### FIXED CODE ###

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

MOD = 998244353

interval = []
for i in range(K):
    intv = [int(x) for x in input().split()]
    interval.append(intv)

dp = [0]*N
diff = [0]*(N-1)
dp[0] = 1
diff[0] = -1

for i in range(N-1):
    for L,R in interval:
        if L <= N-1 - i:
            diff[i+L-1] += dp[i]
        if R+1 <= N-1 - i:
            diff[i+R] -= dp[i]
    dp[i+1] = dp[i] + diff[i]
    dp[i+1] %= MOD

print(dp[N-1])
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
for i in range(N):
	A[i] = A[i]%M

b = 0
c = 0
count = 0
for i in range(N):
	b = b+A[i]
	c = b
	if c%M == 0:
		count = count + 1
	for j in range(N-i-1):
		c = c - A[j] + A[j+i+1]
		if c%M == 0:
			count = count + 1
			
print(count)


### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = [0 for i in range(N+1)]
B[0] = 0
C = {"0":1}
for i in range(N):
	B[i+1] = (B[i]+A[i])%M
	if str(B[i+1]) in C.keys():
		C[str(B[i+1])] = C[str(B[i+1])] + 1
	else:
		C[str(B[i+1])] = 1
	
out = 0
for j in C.values():
	out = out + int(j*(j-1)/2)

print(out)
### BUGGY CODE ###

def main():
    n=int(raw_input())
    ta=[map(int,raw_input().split()) for _ in xrange(n)]
    for i in xrange(1,n):
        tmp1=ta[i][0]
        tmp2=ta[i][1]
        if ta[i-1][0]>ta[i][0]:
            a=ta[i-1][0]/ta[i][0]
            while 1:
                tmp1=ta[i][0]*a
                tmp2=ta[i][1]*a
                if ta[i-1][0]<=tmp1 and ta[i-1][1]<=tmp2:
                    break
                a+=1
        if ta[i-1][1]>ta[i][1]:
            a=ta[i-1][1]/ta[i][1]
            while 1:
                tmp1=ta[i][0]*a
                tmp2=ta[i][1]*a
                if ta[i-1][0]<=tmp1 and ta[i-1][1]<=tmp2:
                    break
                a+=1
        ta[i][0]=tmp1
        ta[i][1]=tmp2
    print(ta[n-1][0]+ta[n-1][1])
main()

### FIXED CODE ###

def main():
    n=int(raw_input())
    ta=[map(int,raw_input().split()) for _ in xrange(n)]
    for i in xrange(1,n):
        if ta[i-1][0]>ta[i][0] and ta[i-1][1]>ta[i][1]:
            mx=max((ta[i-1][0]-1)/ta[i][0]+1,(ta[i-1][1]-1)/ta[i][1]+1)
            ta[i][0]=ta[i][0]*mx
            ta[i][1]=ta[i][1]*mx
        elif ta[i-1][0]>ta[i][0]:
            ta[i][1]=ta[i][1]*((ta[i-1][0]-1)/ta[i][0]+1)
            ta[i][0]=ta[i][0]*((ta[i-1][0]-1)/ta[i][0]+1)
        elif ta[i-1][1]>ta[i][1]:
            ta[i][0]=ta[i][0]*((ta[i-1][1]-1)/ta[i][1]+1)
            ta[i][1]=ta[i][1]*((ta[i-1][1]-1)/ta[i][1]+1)
    print(ta[n-1][0]+ta[n-1][1])
main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

class WarshallFloyd:
    def __init__(self,n):
        self.dist = {}
        for i in range(n-1):
            for j in range(i,n):
                self.dist[(i,j)] = 1e100

    def unite(self,x,y,c):
        if x == y:
            return False
        elif x > y:
            x,y = y,x
        if self.dist[(x,y)] <= c:
            return False
        else:
            for i in range(n-1):
                for j in range(i+1,n):
                    self.dist[(i,j)] = min(self.d(i,j), self.d(i,x) + c + self.d(y,j), self.d(i,y) + c + self.d(x,j))

    def d(self,x,y):
        if x == y:
            return 0
        if x > y:
            x,y = y,x
        return self.dist[(x,y)]

n,m = map(int,input().split())
ABC = [tuple() for _ in range(m)]
wf = WarshallFloyd(n)
for i in range(m):
    a,b,c = map(int,input().split())
    wf.unite(a-1,b-1,c)
    ABC[i] = (a-1,b-1,c)
ans = 0
for a,b,c in ABC:
    ans += (c > wf.d(a,b))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])

n,m = map(int,input().split())
ABC = [tuple() for _ in range(m)]
wf = WarshallFloyd(n)
for i in range(m):
    a,b,c = map(int,input().split())
    wf.path(a-1,b-1,c)
    ABC[i] = (a-1,b-1,c)
ans = 0
wf.build()
for a,b,c in ABC:
    ans += (c > wf.d[a][b])
print(ans)
### BUGGY CODE ###

N = int(input())

ans = 0

for a in range(1, N):
    cnt = 0
    for b in range(1, N):
        if a * b < N:
            if a < b:
                cnt += 2
            elif a == b:
                cnt += 1
        else:
            break
    
    ans += cnt

print (ans)

### FIXED CODE ###

import math

N = int(input())

ans = 0

for a in range(1, N):
    cnt = 0
    for b in range(a, N):
        if a * b < N:
            if a < b:
                cnt += 2
            elif a == b:
                cnt += 1
        else:
            break
    ans += cnt

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

import re
def cal():
    x = input()
    a = re.compile('ST')
    while True:
        pre = len(x)
        x = a.sub('', x)
        if len(x) == pre:
            break
    print(len(x))

cal()


### FIXED CODE ###

x = input()
ans = []

for i in x:
    if i == 'S':
        ans.append(i)
    else:
        if len(ans) == 0 or ans[-1] == 'T':
            ans.append(i)
        else:
            ans.pop()
print(len(ans))
### BUGGY CODE ###

n = int(input())
left = 0
right = n
print(left, flush=True)
sl = input()
if sl[0] == "V":
    quit()
while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    sm = input()
    if sm[0] == "V":
        quit()
    if ((m - left) % 2 == 1) ^ (sl == sm):
        left = mid
        sl = sm
    else:
        n = m



### FIXED CODE ###

n = int(input())

left = 0
right = n
print(left, flush=True)
sl = input()
if sl[0] == "V":
    quit()
while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    sm = input()
    if sm[0] == "V":
        quit()

    if ((mid - left) % 2 == 1) ^ (sl == sm):
        left = mid
        sl = sm
    else:
        right = mid
### BUGGY CODE ###

N, M, K = map(int, input().split())

time_A = list(map(int, input().split()))
time_B = list(map(int, input().split()))
max_books = 0

for i in range(1, K+1):
    num_books = 0
    allot_to_A = i
    allot_to_B = K-i

    for j in range(len(time_A)):
        if time_A[j] <= allot_to_A:
            allot_to_A -= time_A[j]
            num_books += 1
        else:
            break
    for k in range(len(time_B)):
        if time_B[k] <= allot_to_B:
            allot_to_B -= time_B[k]
            num_books += 1
        else:
            break

    max_books = max(max_books, num_books)

print(max_books)


### FIXED CODE ###

N, M, K = map(int, input().split())

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)

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

#!/usr/bin/env python3
import sys
from queue import PriorityQueue
try:
    from typing import List, Tuple, Dict
except ImportError:
    pass
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


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

hoge = 0
for i in range(N):
    for j in range(N):
        hoge += 1


left_queue = PriorityQueue()  # type: PriorityQueue[Tuple[int, None]]

for i in range(N):
    item = (a[i], None)
    left_queue.put(item)


score = sum(a[:N])
left_scores = [score]

for i in range(N, 2*N):
    b, none = left_queue.get()
    if a[i] < b:
        item = (b, None)
        dscore = 0
    else:
        item = (a[i], None)
        dscore = a[i] - b
    left_queue.put(item)
    score += dscore
    left_scores.append(score)


right_queue = PriorityQueue()  # type: PriorityQueue[Tuple[int, None]]

for i in range(2*N, 3*N):
    item = (-a[i], None)
    right_queue.put(item)


score = - sum(a[2*N:])
right_scores = [score]

for i in range(2*N-1, N-1, -1):
    b, none = right_queue.get()
    if -a[i] < b:
        item = (b, None)
        dscore = 0
    else:
        item = (-a[i], None)
        dscore = -a[i] - b
        # debug(a[i], b, i)
    right_queue.put(item)
    # debug(item, score, dscore)
    score += dscore
    right_scores.append(score)


scores = []
for i in range(N+1):
    scores.append(left_scores[i] + right_scores[N-i])

debug(scores)
print(max(scores))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from queue import PriorityQueue
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


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


left_queue = PriorityQueue()

for i in range(N):
    item = (a[i], None)
    left_queue.put(item)


score = sum(a[:N])
left_scores = [score]

for i in range(N, 2*N):
    b, none = left_queue.get()
    if a[i] < b:
        item = (b, None)
        dscore = 0
    else:
        item = (a[i], None)
        dscore = a[i] - b
    left_queue.put(item)
    score += dscore
    left_scores.append(score)


right_queue = PriorityQueue()

for i in range(2*N, 3*N):
    item = (-a[i], None)
    right_queue.put(item)


score = - sum(a[2*N:])
right_scores = [score]

for i in range(2*N-1, N-1, -1):
    b, none = right_queue.get()
    if -a[i] < b:
        item = (b, None)
        dscore = 0
    else:
        item = (-a[i], None)
        dscore = -a[i] - b
        # debug(a[i], b, i)
    right_queue.put(item)
    # debug(item, score, dscore)
    score += dscore
    right_scores.append(score)


scores = []
for i in range(N+1):
    scores.append(left_scores[i] + right_scores[N-i])

debug(scores)
print(max(scores))
### BUGGY CODE ###

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

L.sort(reverse=True)

sum = 0

for i in range(N):
    a = L[i]
    for j in range(i+1,N):
        b = L[j]
        for k in range(j+1,N):
            c = L[k]
            if a < b+c:
                sum = sum + 1
            else:
                break

print sum


### FIXED CODE ###

import bisect

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

    ans = 0
    L = sorted(L)

    for i in range(N):
        a = L[i]
        for j in range(i+1, N):
            b = L[j]
            target = a+b

            c = bisect.bisect_left(L, target)
            ans = ans + (c-j-1)

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

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

d = {}
def kitaichi(n):
	if n in d.keys(): return d[n]
	else:
		sum = n * (n+1) / 2
		d[n] = sum / n
		return d[n]

idx = 0
mx = 0
for i in range(len(p)):
	pp = p[i:i+k]
	if len(pp) != k: break
	if mx < sum(pp):
		mx = sum(pp)
		idx = i

ans = 0
for i in p[idx:idx+k]:
	ans += kitaichi(i)

print(ans)

### FIXED CODE ###

from itertools import accumulate
n, k = map(int, input().split())
p = [-~int(i)/2 for i in input().split()]
a = [0] + list(accumulate(p))
print(max(j-i for i, j in zip(a, a[k:])))
### BUGGY CODE ###

A, B = [int(i) for i in input().split()]
calcu = [0 for i in range(40)]

for n in range(A, B+1):
    i=0
    while n>0:
        calcu[i] = (calcu[i] + (n%2)) %2
        n = n//2
        i += 1

ans=0
for i in range(40):
    if calcu[i]==1:
        ans += 2**i
    i += 1

print(ans)


### FIXED CODE ###

A, B = [int(i) for i in input().split()]


def xor(a,b):
    sum=0
    i=0
    while(b>0):
        sum += (2**i) * ((a%2 + b%2)%2)
        a = a//2
        b = b//2
        i += 1
    return sum



def f(n):
    m=(n+1)//2
    if n%2==0:
        if m%2==0:
            return n
        else:
            return n+1
    else:
        if m%2==0:
            return 0
        else:
            return 1

if A==0:
    print(f(B))
else:
    print(f(A-1) ^ f(B))
### BUGGY CODE ###

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

A.append(0)

def calc_total_amount(a_list, k):
  
  pos = 0
  total_amount = 0
  
  for i in range(n+1):
    if i == k: continue
  
    total_amount += abs(a_list[i] - pos)
    pos = a_list[i]

  return(total_amount)

for i in range(n):
  print(calc_total_amount(A, i))

### FIXED CODE ###

n = int(input())
A = [0] + list(map(int, input().split())) + [0]

D = [abs(A[i+1]-A[i]) for i in range(len(A)-1)]
base = sum(D)

for i in range(n):
  print(base-D[i]-D[i+1]+abs(A[i+2]-A[i]))
### BUGGY CODE ###

import itertools
from collections import defaultdict as dict
d = dict(int)
 
N = int(input())
S = [int(_) for _ in input()]
s = list(itertools.combinations(S, 3))
 
for j in range(len(s)):
 
    # カウントアップ
    d[s[j]] += 1
 
print(len(d))

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
# 000 - 999 まで全探索
for i in range(1000):
    t = str(i).zfill(3)

    # 1桁目が存在するか
    if t[0] in S:
        t1 = S.index(t[0])
        # 2桁目を1桁目のidx + 1から探す
        if t[1] in S[t1 + 1:]:
            # 1桁目のidx + 2桁目のidx + 1 桁目から3文字目を探す
            t2 = t1 + S[t1 + 1:].index(t[1]) + 1
            if t[2] in S[t2 + 1:]:
                ans += 1

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

N=int(input())
S=input()
ans=0
for i in range(N):
    tmp=S[:i].count("E")+S[i+1:].count("W")
    if tmp>ans:
        ans=tmp
ans=N-1-ans
print(ans)


### FIXED CODE ###

N=int(input())
S=input()
S="N"+S+"N"
ans=0
E=0
W=S.count("W")
for i in range(1,N+1):
    if S[i-1]=="E":
        E+=1
    if S[i]=="W":
        W-=1
    tmp=E+W
    if tmp>ans:
        ans=tmp
ans=N-1-ans
print(ans)
### BUGGY CODE ###

class BellmanFord():
	def __init__(self, adj, start):
		self.adj = adj
		self.start = start
		self.size = len(adj)
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0

	def solve(self):
		for _ in range(self.size-1):
			for x in range(self.size):
				for y, w in self.adj[x]:
					if self.dist[y] > self.dist[x] + w:
						self.dist[y] = self.dist[x] + w
		return

	#負閉路のせいでgoalへの距離が-infになるか
	def NegativeCycleToGoal(self, goal):
		res = self.dist[goal]
		for _ in range(self.size):
			for x in range(self.size):
				for y, w in self.adj[x]:
					if self.dist[y] > self.dist[x] + w:
						self.dist[y] = self.dist[x] + w
		if res != self.dist[goal]:
			return True
		else:
			return False

	def GetDistance(self, goal):
		return self.dist[goal]

n, m, p = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
	a, b, c = map(int, input().split())
	adj[a-1].append((b-1, -c+p))

bf = BellmanFord(adj, 0)
bf.solve()
if bf.NegativeCycleToGoal(n-1):
	print("-1")
else:
	print(max(-bf.GetDistance(n-1), 0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**4)
def input():
	return sys.stdin.readline()[:-1]

class BellmanFord():
	def __init__(self, adj, start, size):
		self.adj = adj
		self.start = start
		self.size = size
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0

	def solve(self):
		for _ in range(self.size-1):
			for x in range(self.size):
				for y, w in self.adj[x]:
					if s_reachable[x] and s_reachable[y] and g_reachable[x] and g_reachable[y]:
						if self.dist[y] > self.dist[x] + w:
							self.dist[y] = self.dist[x] + w
		for x in range(self.size):
			for y, w in self.adj[x]:
				if s_reachable[x] and s_reachable[y] and g_reachable[x] and g_reachable[y]:
					if self.dist[y] > self.dist[x] + w:
						return False

		return True

	def GetDistance(self, goal):
		return self.dist[goal]

n, m, p = map(int, input().split())
adj = [[] for _ in range(n)]
adj_rev = [[] for _ in range(n)]

for _ in range(m):
	a, b, c = map(int, input().split())
	adj[a-1].append((b-1, -c+p))
	adj_rev[b-1].append(a-1)

s_reachable = [False for _ in range(n)]
s_reachable[0] = True
g_reachable = [False for _ in range(n)]
g_reachable[n-1] = True

def dfs_s(x):
	for v, w in adj[x]:
		if not s_reachable[v]:
			s_reachable[v] = True
			dfs_s(v)
	return

def dfs_g(x):
	for v in adj_rev[x]:
		if not g_reachable[v]:
			g_reachable[v] = True
			dfs_g(v)
	return

dfs_s(0)
dfs_g(n-1)

bf = BellmanFord(adj, 0, n)
if not bf.solve():
	print(-1)
else:
	print(max(-bf.GetDistance(n-1), 0))
### BUGGY CODE ###

n = int(input())
g = [[] for x in range(n+1)]
s = []
for _ in range(n-1):
    a,b = [int(x) for x in input().split()]
    g[a].append(b)
    g[b].append(a)
    s.append([a,b])

from collections import deque
color = [[-1]*(n+1) for x in range(n+1)]
index = []
q = deque()
q.append([1,0])
ans = 0
while q:
    num = 0
    p = q.popleft()
    for i in g[p[0]]:
        if color[p[0]][i]==-1:
            num += 1
            if p[1]==num:
                num += 1
            color[p[0]][i] = num
            color[i][p[0]] = num
            q.append([i,num])
            ans = max(ans,num)

print(ans)
for a,b in s:
    print(color[a][b])
    

### FIXED CODE ###

n = int(input())
g = [[] for _ in range(n)]
z = []
for _ in range(n-1):
    a,b = [int(x)-1 for x in input().split()]
    g[a].append(b)
    g[b].append(a)
    if a<b:
        z.append((a,b))
    else:
        z.append((b,a))

from collections import deque

parent = [0]*n
mc = 0
en = dict()

q = deque()
used = [0]*n
q.append(0)
used[0] = 1
while q:
    p = q.popleft()
    color = 0
    for i in g[p]:
        if used[i] != 1:
            color += 1
            used[i] = 1
            if color==parent[p]:
                color += 1
            if p<i:
                en[(p,i)]=color
            else:
                en[(i,p)]=color
            parent[i] = color
            q.append(i)
    mc = max(mc,color)

print(mc)
for i in z:
    print(en[i])
### BUGGY CODE ###

from functools import reduce

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

ans = reduce(lambda x, y: x * y, a)
print(ans) if ans <= 10 ** 18 else print(-1)


### FIXED CODE ###

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

if 0 in a:
    print(0)
else:
    ans = 1
    for i in a:
        ans *= i
        if ans > 10 ** 18:
            print(-1)
            exit()

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

has_duplicates= lambda seq:len(seq) == len(set(seq))
def main():
    n=int(input())
    l=list(map(int,input().split()))
    tel=[-1,-1,-1]
    temp=0
    bn=0
    tc=0
    pc=0
    i=0
    while len(bin(i))-3<n:
        if str(bin(i)).count('1')==3:
            bn=bin(i)
            tc=0
            tel=[-1,-1,-1]
            for j in range(len(str(bn)[2:])):
                if (i>>j)&1:
                    tel[tc]=l[n-j-1]
                    tc+=1
            if has_duplicates(tel):
                tel.sort()
                if tel[0]+tel[1]>tel[2]:
                    pc+=1
        i+=1
    print(pc)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n=int(input())
    l=list(map(int,input().split()))
    ans=0
    for i in range(n):
        for k in range(i+1,n):
            for j in range(k+1,n):
                temp=[l[i],l[k],l[j]]
                if len(set(temp))==len(temp):
                    temp.sort()
                    if temp[0]+temp[1]>temp[2]:
                        ans+=1
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

dp=[float('inf')]*(h+1) #0-9
dp[h]=0
mini=float('inf')
for i in reversed(range(0,h+1)):
    if dp[i]==float('inf'):
        continue
    for ata,mp in a:
        if i-ata<=0:
            tmp=dp[i]+mp
            mini=min(mini,tmp)
            continue
        dp[i-ata]=min(dp[i-ata],dp[i]+mp)
print(mini)

### FIXED CODE ###


h,n=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(n)]
inf=10**9
dp=[inf]*(h+1) #0-9
dp[0]=0
mini=inf
for i in range(h+1):
    if dp[i]==inf:
        continue
    for ata,mp in a:
        if i+ata>=h:
            tmp=dp[i]+mp
            mini=min(mini,tmp)
            continue
        dp[i+ata]=min(dp[i+ata],dp[i]+mp)
print(mini)