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

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

number_of_items=0
for X in range(min(A)-1, max(A)+1):
    if number_of_items < A.count(X)+A.count(X-1)+A.count(X+1):
        number_of_items = A.count(X)+A.count(X-1)+A.count(X+1)
print(number_of_items)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
bucket=[0]*(max(A)+1)
answer=0
for number in A:
    bucket[number]+=1
if len(bucket)<3:
    answer=sum(bucket)
for i in range(1,max(A)):
    candidate=bucket[i-1]+bucket[i]+bucket[i+1]
    if candidate>answer:
        answer=candidate
print(answer)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
num = list(sorted(A, reverse=True))

count = 0
for i in range(n - 1):
    count += len(A) - 1 - A.index(num[i])
    A.remove(num[i])

print(count)

### FIXED CODE ###

def merge(A, left, mid, right):
    global count
    banpei = 1000000001
    L = A[left:mid]
    l = len(L)
    L += [banpei]
    R = A[mid:right] + [banpei]

    i, j = 0, 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            count += l - i
    return count


def merge_Sort(A, left, right):
    if 1 < right - left:
        mid = (left + right) // 2
        merge_Sort(A, left, mid)
        merge_Sort(A, mid, right)
        merge(A, left, mid, right)

n = int(input())
A = list(map(int, input().split()))
count = 0
merge_Sort(A, 0, n)
print(count)
### BUGGY CODE ###

K = int(input())
like = 7
ans = -1
for i in range(1, K+1):
    if like % K == 0:
        ans = i
        break
    like =like*10+7
print(ans)

### FIXED CODE ###

K = int(input())
like = 7
ans = -1
for i in range(K):
    if like % K == 0:
        ans = i+1
        break
    like = (like*10+7) % K
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def dp(i):
  for a,b in AB:
    T=C[i-a if i>a else 0]+b
    C[i]=T if T<C[i] else C[i]

H,N=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]
C=[0]+[10**8]*H

for i in range(1,H+1):
  dp(i)

print(C[H])


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
  def dp(i):
    for a,b in AB:
      T=C[i-a if i>a else 0]+b
      C[i]=T if T<C[i] else C[i]

  H,N=map(int,input().split())
  AB=[list(map(int,input().split())) for _ in range(N)]
  C=[0]+[10**8]*H

  for i in range(1,H+1):
    dp(i)

  print(C[H])

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

n = int(input())
cnt = 0
for i in range(1, n+1):
    hoge = int(n//i)
    cnt += (hoge + 1) * i * hoge // 2
print(cnt)

### FIXED CODE ###

n = int(input())
cnt = 0
for i in range(1, n+1):
    hoge = n//i
    cnt += (hoge + 1) * i * hoge / 2
print(int(cnt))
### BUGGY CODE ###

n = int(input())
V = list(map(int,input().split()))
cnt = 0
cnt1 = 0
for i in range(n-2):
  if len(set(V)) == 1:
    print(n//2)
    exit()
  if V[i] == V[i+2] and i%2==0:
    cnt += 1
  elif V[i] == V[i+2] and i%2==1:
    cnt1 += 1
print(max(cnt,cnt1)-min(cnt,cnt1))

### FIXED CODE ###

from collections import Counter
N = int(input())
V = list(map(int,input().split()))
v1 = V[0::2]
v2 = V[1::2]
v1c = Counter(v1).most_common()
v2c = Counter(v2).most_common()
v1c.append((0,0))
v2c.append((0,0))
if v1c[0][0]==v2c[0][0]:
    print(min(N-v1c[0][1]-v2c[1][1],N-v1c[1][1]-v2c[0][1]))
else:
    print(N-v1c[0][1]-v2c[0][1])
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
P = [K]* N
def calc(n):
    return n - 1

for i in range(Q):
  P = list(map(calc, P))
  P[A[i] - 1] += 1

for p in P:
  if p > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
P = [K - Q]* N

for i in range(Q):
  P[A[i] - 1] += 1

for p in P:
  if p > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

n = int(input())

S = 0
for i in range(1, 200000):
    S += n % 10
    if n // 10  == 0:
        break
    else:
        n //= 10

if S % 9 == 0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

n = input()

S = 0
for i in range(len(n)):
    S += int(n[i])

if S % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import collections
import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
ans = 0
for k, v in c.items():
    if v > 1:
        ans += combinations_count(v, 2)
total_ans = ans

for k_ball in A:
    if c[k_ball] > 2:
        print(
            total_ans
            - (combinations_count(c[k_ball], 2) - combinations_count(c[k_ball] - 1, 2))
        )
    elif c[k_ball] > 1:
        print(total_ans - 1)
    else:
        print(total_ans)

### FIXED CODE ###

# 解き直し
import collections

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

total = 0
for v in c.values():
    total += v * (v - 1) // 2

for k_ball in A:
    cnt = c[k_ball]
    print(total - (cnt * (cnt - 1) // 2) + ((cnt - 1) * (cnt - 2) // 2))
### BUGGY CODE ###


def keisan(a):
    a.sort(reverse = True)
    ans = 0
    for i in range(0,n,2):
        if a.count(a[i]) >= 4:
            ans = a[i]*a[i]
            break
        elif a.count(a[i]) >=2:
            
            for j in range(i+a.count(a[i]),n,2):
                if a.count(a[j]) >=2:
                    ans = a[i]*a[j]
                    break
            break
    print(ans)

n = int(input())
in_ = [int(i) for i in input().split()]
keisan(in_)

### FIXED CODE ###

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

a.sort(reverse = True)
ans = 0
b = a.copy()
b = list(set(b))
b.sort(reverse = True)
c = [0]*len(b)
j = 0
c[j] = 1
for i in range(1,n):
    if a[i-1] == a[i]:
        c[j] +=1
    else:
        j+=1
        c[j] +=1
for i in range(len(b)):
    if c[i] >= 4:    
        
        ans = b[i]*b[i]
        break
    elif c[i] >= 2:
        for j in range(i+1,len(b)):
            if c[j] >= 2:
                ans = b[i]*b[j]
                break
        break
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
a_b = [list(input().split()) for i in range(N)]
big_array = []

for i in range(N):
    big_array += [a_b[i][0]] * int(a_b[i][1])

print(sorted(big_array)[K-1])


### FIXED CODE ###

N, K = map(int, input().split())
a_b = [list(map(int, input().split())) for i in range(N)]
a_b.sort()
index = 0

for i in range(N):
    index += a_b[i][1]
    if index >= K:
        print(a_b[i][0])
        exit()
### BUGGY CODE ###

n = int(input())
dict = []
for i in range(n):
    order = input().split()
    if order[0] == "insert":
        dict.append(order[1])
    else:
        if order[1] in dict:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

from collections import deque

n = int(input())
dict = {}
for i in range(n):
    order = input().split()
    if order[0] == "insert":
        dict[order[1]] = i
    else:
        if order[1] in dict:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###


def solve(s,e):
	res=0
	for i in range(s,e+1):
		res+=train[i][e]-train[i][s-1]
	return res

city,dnum,qnum=map(int,input().split())

train=[[0 for i in range(city+1)] for i in range(city+1)]

for i in range(dnum):
	l,r=map(int,input().split())
	train[l][r]+=1

for i in range(city+1):
	tmp=0
	for j in range(city+1):
		tmp+=train[i][j]
		train[i][j]=tmp
		
	
querry=[list(map(int,input().split())) for i in range(qnum)]

for q in querry:
	print(solve(*q))

### FIXED CODE ###

def main():
    n, m, Q = map(int, input().split())
    Train= [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(m):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        Train[l][r] += 1
    
    P_Train = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        tmp = 0
        for j in range(n):
            tmp += Train[i][j]
            P_Train[i][j] = tmp

    for i in range(Q):
        p, q = map(int, input().split())
        p, q = p - 1, q - 1
        ans = solve(P_Train, n, p, q)
        print(ans)

def solve(P_Train, n, p, q):
    ans = 0
    for i in range(p, q + 1):
        if  p - 1 < 0:
            ans += P_Train[i][q]
        else:
            ans += P_Train[i][q] - P_Train[i][p - 1]
    return ans


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

S = input()
mod = 10**9+7

N = len(S)
A1,A2,A3,C1,C2,C3 = [1]*N,[1]*N,[1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    if S[i-1]=="?":
        aa += 1
        A3[i] = A3[i-1]*3
    else:
        A3[i] = A3[i-1]
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    if S[N-1-i+1]=="?":
        cc += 1
        C3[N-1-i] = C3[N-1-i+1]*3
    else:
        C3[N-1-i] = C3[N-1-i+1]
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i]=="B" or S[i]=="?":
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (A3[i]//3*(A1[i]*3 + A2[i])) % mod 
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (C3[i]//3*(C1[i]*3 + C2[i])) % mod
        Ans += ta*tc

print(Ans % mod)

### FIXED CODE ###

S = input()
mod = 10**9+7

N = len(S)
A1,A2,C1,C2 = [1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i] in ("B","?"):
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = pow(3,A2[i],mod)*A1[i] + pow(3,A2[i]-1,mod)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = pow(3,C2[i],mod)*C1[i] + pow(3,C2[i]-1,mod)*C2[i]
        Ans += ta*tc
        Ans %= mod

print(Ans)
### BUGGY CODE ###

import queue
n,m=map(int,input().split())
vis,ci,cb,cc=[0]*(n+1),0,0,0
g=[[] for i in range(n+1)]
def dfs(x):
	stk,flag=queue.LifoQueue(),True
	stk.put((x,1))
	while not stk.empty():
		u,col=stk.get()
		if vis[u]:
			flag&=(vis[u]==col)
			continue
		vis[u]=col
		for i in g[u]:
			stk.put((i,3-col))
	return flag
for i in range(m):
	u,v=map(int,input().split())
	g[u]+=[v]
	g[v]+=[u]
for i in range(1,n+1):
	if vis[i]==0:
		if len(g[i])==0:
			ci+=1
		else:
			if dfs(i):
				cb+=1
			else:
				cc+=1
print(ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb)

### FIXED CODE ###

import queue
n,m=map(int,input().split())
vis,ci,cb,cc=[0]*(n+1),0,0,0
g=[[] for i in range(n+1)]
def dfs(x):
	stk,flag=queue.LifoQueue(),True
	stk.put((x,1))
	while not stk.empty():
		u,col=stk.get()
		if vis[u]:
			flag&=(vis[u]==col)
			continue
		vis[u]=col
		for i in g[u]:
			stk.put((i,3-col))
	return flag
for i in range(m):
	u,v=map(int,input().split())
	g[u]+=[v]
	g[v]+=[u]
for i in range(1,n+1):
	if vis[i]==0:
		if len(g[i])==0:
			ci+=1
		else:
			if dfs(i):
				cb+=1
			else:
				cc+=1
print(ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb)
### BUGGY CODE ###

from collections import deque
def main():
    S = input()
    S = deque([c for c in S])
    Q = int(input())
    rvCt = 0

    head, tail = deque([]), deque([])
    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            rvCt += 1
        else:
            if rvCt % 2 == 1:
                head += S
                head += tail
                S = head
                S.reverse()
                head, tail = deque([]), deque([])
            rvCt = 0
            if query[1] == '1':
                head.appendleft(query[2])
            else:
                tail.append(query[2])

    if rvCt % 2 == 1:
        head += S
        head += tail
        S = head
        S.reverse()
    else:
        head += S
        head += tail
        S = head
    
    print(''.join(S))

main()

### FIXED CODE ###

from collections import deque
def main():
    S = input()
    S = deque([c for c in S])
    Q = int(input())
    rvCt = 0

    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            rvCt += 1
        else:
            doReverse = False
            if rvCt % 2 == 1:
                doReverse = True

            if query[1] == '1':
                if doReverse:
                    S.append(query[2])
                else:
                    S.appendleft(query[2])
            else:
                if doReverse:
                    S.appendleft(query[2])
                else:
                    S.append(query[2])

    if rvCt % 2 == 1:
        S.reverse()
    
    print(''.join(S))

main()
### BUGGY CODE ###

import itertools

N = int(input())
S = input()
S_list = []
for i in range(len(S)):
    S_list.append(S[i])

comb_S_list = list(itertools.combinations(S_list,3))

print(len(set(comb_S_list)))


### FIXED CODE ###

N = int(input())
S = input()
cnt = 0

for i in range(10):
    a = S.find(str(i))
    if a == -1 : continue
    for j in range(10):
        b = S.find(str(j),a+1)
        if b == -1 : continue
        for k in range(10):
            c = S.find(str(k),b+1)
            if c != -1 :
                cnt += 1

print(cnt)
### BUGGY CODE ###

def gcd(p,q):
    while q != 0:
        r = p % q
        p = q
        q = r
    return p
k = int(input())
a = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            a += gcd(gcd(i,j),k)
print(a)

### FIXED CODE ###

def gcd(p,q):
    while q != 0:
        r = p % q
        p = q
        q = r
    return p
k = int(input())
a = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            a += gcd(gcd(i,j),k)
print(a)
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]
s.sort()
p = [s[0]]
for i in range(1,len(s)):
    if s[i] != s[i-1]:
        p.append(s[i])
k = [] 
for i in p:
    k.append(s.count(i))
max_k = max(k)
for i in range(len(p)):
    if k[i] == max_k:
        print(p[i])

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
s.sort()
p = [s[0]]
k = [1]
for i in range(1,len(s)):
    if s[i] != s[i-1]:
        p.append(s[i])
        k.append(1)
    else: k[-1] += 1
max_k = max(k)
for i in range(len(p)):
    if k[i] == max_k:
        print(p[i])
### BUGGY CODE ###

import numpy as np
from collections import deque
import sys
input = sys.stdin.readline

H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(input())

ans = 0


def bfs(x, y):
    global ans
    m = np.full((H, W), -1, dtype=np.int)

    q = deque()
    q.append([y, x, 0])

    while q:
        j, i, v = q.popleft()
        m[j][i] = v
        dj = j + 1
        if dj < H and m[dj][i] == -1 and S[dj][i] == ".":
            q.append([dj, i, v+1])
            if ans < v+1:
                ans = v+1
        dj = j - 1
        if 0 <= dj and m[dj][i] == -1 and S[dj][i] == ".":
            q.append([dj, i, v+1])
            if ans < v+1:
                ans = v+1
        di = i + 1
        if di < W and m[j][di] == -1 and S[j][di] == ".":
            q.append([j, di, v+1])
            if ans < v+1:
                ans = v+1
        di = i - 1
        if 0 <= di and m[j][di] == -1 and S[j][di] == ".":
            q.append([j, di, v+1])
            if ans < v+1:
                ans = v+1


for j in range(H):
    for i in range(W):
        if S[j][i] != ".":
            continue
        bfs(i, j)
print(ans)


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0

        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)
### BUGGY CODE ###

h, w, m = map(int, input().split())
 
mp = []
hp = [0] * h
wp = [0] * w
 
for i in range(m):
    l = list(map(int, input().split()))
    mp.append(l)
    hp[l[0]-1] += 1
    wp[l[1]-1] += 1
 
maxhp = max(hp)
maxwp = max(wp)
hpdex = [i for i, x in enumerate(hp) if x == maxhp]
wpdex = [i for i, x in enumerate(wp) if x == maxwp]
 
for i in range(len(hpdex)):
    for j in range(len(wpdex)):
        if [hpdex[i] + 1, wpdex[j] + 1] not in mp:
            print(maxhp + maxwp)
            exit()
 
print(maxhp + maxwp - 1)

### FIXED CODE ###

h, w, m = map(int, input().split())

mp = set()
hp = [0] * h
wp = [0] * w

for i in range(m):
    a, b = map(int, input().split())
    mp.add((a, b))
    l = [a, b]
    hp[l[0]-1] += 1
    wp[l[1]-1] += 1

maxhp = max(hp)
maxwp = max(wp)
hpdex = [i for i, x in enumerate(hp) if x == maxhp]
wpdex = [i for i, x in enumerate(wp) if x == maxwp]

for i in hpdex:
    for j in wpdex:
        if (i+1, j+1) not in mp:
            print(max(hp) + max(wp))
            exit()

print(max(hp) + max(wp) - 1)
### BUGGY CODE ###

N = int(input())
light_rule = {n:int(input())-1 for n in range(N)}

light = "1"+"0"*(N-1)
target = "0"+"1"+"0"*(N-2)
searched = {light:1}

flag = 0
num = 0
bottun = 0
while True:
    if light == target:
        flag = 1
        break
    num += 1
    idx = bottun
    light = light[:idx]+"0"+light[idx+1:]
    idx = light_rule[bottun]
    light = light[:idx]+"1"+light[idx+1:]
    bottun = light_rule[bottun]
    if searched.get(light):
        break
    else:
        searched[light] = 1
    
if flag:
    print(num)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
light_rule = {n:int(input())-1 for n in range(N)}

light = ["1"]+["0"]*(N-1)

flag = 0
num = 0
bottun = 0
for _ in range(N):
    if light[1] == "1":
        flag = 1
        break
    num += 1
    # print(bottun, light_rule[bottun])
    light[bottun] = "0"
    light[light_rule[bottun]] = "1"
    bottun = light_rule[bottun]
    # print(light)
    
if flag:
    print(num)
else:
    print(-1)
### BUGGY CODE ###

def main():
    s = str(input())
    n = len(s)
    ans = [0] * n
    move = 2 * 10 ** 5
    for i in range(n):
        position = i
        for j in range(move):
            if s[position] == "R":
                position += 1
            else:
                position -= 1
        ans[position] += 1
    print(*ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = str(input())
    n = len(s)
    ans = [0] * n
    for i in range(n):
        if s[i] == "R":
            if i != (n - 1) and s[i + 1] == "L":
                ans[i] += 1
                for j in range(i - 2, -1, -2):
                    if s[j] == "R" and s[j + 1] == "R":
                        ans[i] += 1
                    else:
                        break
            for j in range(i + 2, n, 2):
                if s[j - 1] == "L" and s[j] == "L":
                    ans[i] += 1
                else:
                    break
        else:  # s[i] == "L"
            if i != 0 and s[i - 1] == "R":
                ans[i] += 1
                for j in range(i + 2, n, 2):
                    if s[j - 1] == "L" and s[j] == "L":
                        ans[i] += 1
                    else:
                        break
            for j in range(i - 2, -1, -2):
                if s[j] == "R" and s[j + 1] == "R":
                    ans[i] += 1
                else:
                    break
    print(*ans)


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

import sys
input = sys.stdin.readline

def cmin(a, b, i):
  if a > b:
    dp[i] = b
    return True
  return False

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [sys.maxsize]*N
dp[0] = 0

for i in range(0, N):
  for j in range(1,K+1):
    cmin(dp[i], dp[i-1] + abs(h[i] - h[i-1]), i)
    if i > 1:
      cmin(dp[i], dp[i-j] + abs(h[i] - h[i-j]), i)
print(dp[N-1])    

### FIXED CODE ###

import sys
input = sys.stdin.readline

def cmin(a, b, i):
  if a > b:
    dp[i] = b
    return True
  return False

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [sys.maxsize]*N
dp[0] = 0

for i in range(0, N):
  for j in range(1,K+1):
    cmin(dp[i], dp[i-1] + abs(h[i] - h[i-1]), i)
    if i > 1:
      cmin(dp[i], dp[i-j] + abs(h[i] - h[i-j]), i)
print(dp[N-1])
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split(' ')))
for i in range(1,N+1):
    if int(a.count(i)) > 0:
        print(a.count(i))
    else:
        print(0)

### FIXED CODE ###

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

ans = [0]*N

for i in A:
    ans[i - 1] += 1
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

n = int(input())

uvws = [list(map(int, input().split())) for _ in range(n - 1)]

Li = [0] * 2 + [2] * (n-1)

while 2 in Li:
    for uvw in uvws:
        u, v, w = uvw
        if Li[u] != 2:
            if w % 2 == 0:
                Li[v] = Li[u]
            else:
                Li[v] = 1 - Li[u]
        elif Li[v] != 2:
            if w % 2 == 0:
                Li[u] = Li[v]
            else:
                Li[u] = 1 - Li[v]

for i in range(n):
    print(Li[i+1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def tree_path():
    # 辺と長さが与えられる
    # 頂点1からの各点の距離を計算する
    # 距離が偶数か奇数かで色分け
    sys.setrecursionlimit(100000)
    n = int(input())
    path = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        # 無向グラフ
        path[u].append((v, w))
        path[v].append((u, w))
    # d[0]は使わない
    d = [-1] * (n + 1)

    def walk(i, c):
        if d[i] == -1:
            d[i] = c
            for x, w in path[i]:
                walk(x, c + w)

    walk(1, 0)
    for i in d[1:]:
        print(i % 2)

        
tree_path()
### BUGGY CODE ###


import numpy as np


def main():
    n = int(input().strip())
    l = list(map(int, input().split()))
    l = np.array(l)

    tot = 0
    for i in range(n):
        tot += (l[i] * (np.sum(l[i + 1:n], dtype='int64') % (10 ** 9 + 7))) % (10 ** 9 + 7)
        '''
        if tot >= 10**9 + 7:
            tot %= (10**9 + 7)
        '''

    print(tot % (10 ** 9 + 7))


if __name__ == "__main__":
    main()
    

### FIXED CODE ###



def main():
    n = int(input().strip())
    l = list(map(int, input().split()))
    stack = [0]*n

    totstack = 0
    for i in range(n-1):
        totstack += l[n-i-1]
        stack[n-i-2] = totstack

    tot = 0
    for i in range(n):
        tot += (l[i] * (stack[i] % (10 ** 9 + 7))) % (10 ** 9 + 7)

    print(tot % (10 ** 9 + 7))


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

n = int(input())
s = list(input())
ans = 0
R = []
G = []
B = []


for i in range(n):
    if s[i] == "R":
        R.append(i)
    elif s[i] == "G":
        G.append(i)
    else:
        B.append(i)

ans = len(R) * len(G) * len(B)


for i in R:
    for j in G:
        k = j + (j - i)
        if k in B:
            ans -= 1
        k = i + (i - j)
        if k in B:
            ans -= 1
        k = (i+j)/2
        if k in B:
            ans -= 1

print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
ans = 0
R = []
G = []
B = []


for i in range(n):
    if s[i] == "R":
        R.append(i)
    elif s[i] == "G":
        G.append(i)
    else:
        B.append(i)

ans = len(R) * len(G) * len(B)


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


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

k,s = map(int,input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                cnt += 1
            elif s < x+y+z:
                break
print(cnt)

### FIXED CODE ###

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