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

import heapq
n = int(input())
cost = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
for _ in range(n-1):
    From, To, d = map(int, input().split())
    cost[From][To] = d
    cost[To][From] = d

q, k = map(int, input().split())
dist = [float('inf') for _ in range(n+1)]
dist[k] = 0
next_v = [[0, k]]

while len(next_v):
    v = next_v[0][1]
    for i in range(n+1):
        if dist[i] > dist[v] + cost[v][i]:
            dist[i] = dist[v] + cost[v][i]
            heapq.heappush(next_v, [dist[i], i])
    heapq.heappop(next_v)

for _ in range(q):
    x, y = map(int, input().split())
    print(dist[x]+dist[y])

### FIXED CODE ###

import heapq
def dijkstra(n, edges, s):
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    path = [-1] * n
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u, d in edges[v]:
            if min_dist[u] > min_dist[v] + d:
                min_dist[u] = min_dist[v] + d
                heapq.heappush(next_v, (min_dist[u], u))
                path[u] = v
                
    return min_dist, path

n = int(input())
edges = [[] for _ in range(n)]

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


q, k = map(int, input().split())
dist, _ = dijkstra(n, edges, k-1)

for _ in range(q):
    x, y = map(int, input().split())
    print(dist[x-1] + dist[y-1])
### BUGGY CODE ###

def parent(n):
    return (n+1)/2-1

def left(n):
    return (n+1)*2-1

def right(n):
    return (n+1)*2

def max_heapify(A, i):
    global pt
    l = left(i)
    r = right(i)
    largest = i
    if l <= pt and A[largest] < A[l]:
        largest = l
    if r <= pt and A[largest] < A[r]:
        largest = r

    if largest != i:
        A[largest],A[i] = A[i],A[largest]
        max_heapify(A,largest)

def build_max_heap(A):
    for i in reversed(xrange((len(A)-1)/2+1)):
        max_heapify(A,i)

def up_heap(A,i):
    p = parent(i)
    if p >= 0 and A[p] < A[i]:
        A[p],A[i] = A[i],A[p]
        up_heap(A,p)

def extract_max(A):
    global pt
    ret = A[0]
    A[0] = A[pt]
    pt -= 1
    max_heapify(A,0)
    return ret


heap = [0]*2000000
pt = -1
while True:
    c = raw_input()
    if c[0] == 'i':
        n = int(c[7:])
        pt += 1
        heap[pt] = n
        up_heap(heap,pt)
    elif c[:2] == 'ex':
        print extract_max(heap)
    else:
        break

### FIXED CODE ###

from sys import stdin

def max_heapify(A, i):
    l = i*2
    r = i*2+1
    largest = i
    if l <= A[0] and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= A[0] and A[largest] < A[r]:
        largest = r

    if largest != i:
        A[largest],A[i] = A[i],A[largest]
        max_heapify(A,largest)

heap = [0]*2000000
for c in stdin:
    if c[0] == 'i':
        heap[0] += 1
        heap[heap[0]] = int(c[7:])
        i = heap[0]
        p = i/2
        while p > 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = i/2
    elif c[1] == 'x':
        print heap[1]
        heap[1] = heap[heap[0]]
        heap[0] -= 1
        max_heapify(heap,1)
    else:
        break
### BUGGY CODE ###

def t(s):
    a = [''.join(sorted(list(i))) for i in s]
    b = set(a)
    r = 0
    for i in b:
        n = a.count(i)
        r += n * (n - 1) / 2
    return int(r)


if __name__ == '__main__':
    n = int(input())
    print(t([input() for i in range(n)]))


### FIXED CODE ###

def t(s):
    a = [''.join(sorted(i)) for i in s]
    b = {}
    r = 0
    for i in a:
        if i in b.keys():
            r += b[i]
            b[i] += 1
        else:
            b[i] = 1
    return int(r)


if __name__ == '__main__':
    n = int(input())
    print(t([input() for i in range(n)]))
### BUGGY CODE ###

N = int(input())

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

a.sort()

#print (a)

a = a + [-2]
ans = 0
for i in range(N):
    count = 0
    j = 0
    while a[i] <= a[i+j] and a[i+j] <= a[i] + 2:
        count += 1
        j += 1
    ans = max(ans, count)

print (ans)





### FIXED CODE ###

N = int(input())

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

a.sort()

#print (a)

a = [-2] + a + [-8]

lst = []
count = 1
for i in range(1,N+2):
    if a[i] == a[i-1]:
        count += 1
    else:
        lst += [[a[i-1], count]]
        count = 1

# print (lst)

ans = 0
lst += [[-10,0], [-20,0]]
# print (lst)
for i in range(0, len(lst)-2):
    count = lst[i][1]
    if lst[i][0] + 1 == lst[i+1][0]:
        count += lst[i+1][1]
        if lst[i][0] +2 == lst[i+2][0]:
            count += lst[i+2][1]
    ans = max(ans, count)

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

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

def main():
  n = int(input())
  board = []
  for _ in range(n):
    board.append(list(input().strip()))
  
  def judge(ia):
    for i in range(n):
      for j in range(i+1, n):
        if board[(i+ia)%n][j] != board[(j+ia)%n][i]:
          return False
    return True
  
  cnt = 0 
  for ia in range(n):
    if judge(ia):
      cnt += 1
  print(n * cnt)
  
if __name__=='__main__':
  main()



### FIXED CODE ###

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

def main():
  n = int(input())
  board = []
  for _ in range(n):
    board.append(list(input().strip()))
  
  def judge(ia):
    for i in range(n):
      for j in range(i+1, n):
        if board[(i+ia)%n][j] != board[(j+ia)%n][i]:
          return False
    return True
  
  cnt = 0 
  for ia in range(n):
    if judge(ia):
      cnt += 1
  print(n * cnt)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

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

### FIXED CODE ###

n, q = map(int, input().split())
s=input()
d=[0]*n
c=0
for i in range(n-1):
  if s[i:i+2]=="AC":
    c+=1
  d[i+1]=c
for i in range(q):
  l,r= map(int, input().split())
  print(d[r-1]-d[l-1])
### BUGGY CODE ###

import sys
from heapq import heappush, heappop, merge, heapify

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
works = [[] for _ in range(M+1)]
#Bが報酬
for _ in range(N):
    a, b = lr()
    if a <= M:
        works[a].append(-b)

cand = []
answer = 0
for i in range(1, M+1):
    cand = list(merge(cand, works[i]))
    heapify(cand)
    if cand:
        answer -= heappop(cand)

print(answer)


### FIXED CODE ###

import heapq

n,m=map(int,input().split())
jobs=[[] for _ in range(m)]
for i in range(n):
    d,r=map(int,input().split())
    if d-1<m:
        jobs[d-1].append(-r)
rewards=0
heap=[]
for i in range(m):
    for reward in jobs[i]:
        heapq.heappush(heap,reward)
    if len(heap)>0:
        rewards+=-heapq.heappop(heap)

print(rewards)
### BUGGY CODE ###

H, W, K = map(int, input().split())
items = []

start = []
diff = float("inf")
p = []
prev = [[False] * W for _ in range(H)]
for i in range(H):
    items.append(list(input()))
    for j in range(W):
        s = items[i][j]
        if s == "S":
            start = [i, j]
            diff = min(diff, min(i, H - 1 - i, min(j, W - 1 - j)))
            p = [i, j]
            prev[i][j] = True

from collections import deque

que = deque([])

dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]

for i in range(4):
    x = dx[i]
    y = dy[i]
    if 0 <= start[0] + y <= H - 1 and 0 <= start[1] + x <= W - 1:
        tmp = items[start[0] + y][start[1] + x]
        if tmp == ".":
            que.append((start[0] + y, start[1] + x))
k = K
while len(que) != 0 and k != 0:
    que2 = deque([])
    while len(que) != 0:
        q = que.popleft()
        prev[q[0]][q[1]] = True
        if min(diff, min(q[0], H - 1 - q[0], min(q[1], W - 1 - q[1]))) < diff:
            diff = min(diff, min(q[0], H - 1 - q[0], min(q[1], W - 1 - q[1])))
            p = (q[0], q[1])

        for i in range(4):
            x = dx[i]
            y = dy[i]
            if 0 <= q[0] + y <= H - 1 and 0 <= q[1] + x <= W - 1:
                if prev[q[0] + y][q[1] + x]:
                    continue
                tmp = items[q[0] + y][q[1] + x]
                if tmp == ".":
                    que2.append((q[0] + y, q[1] + x))
    k -= 1
    que = que2

ans = 1
if diff == 0:
    print(ans)
else:
    print(ans + (K - 1 + diff) // K)


### FIXED CODE ###

H, W, K = map(int, input().split())
items = []

start = []
diff = float("inf")
p = []
prev = [[False] * W for _ in range(H)]
for i in range(H):
    items.append(list(input()))
    for j in range(W):
        s = items[i][j]
        if s == "S":
            start = [i, j]
            diff = min(diff, min(i, H - 1 - i, min(j, W - 1 - j)))
            p = [i, j]
            prev[i][j] = True

from collections import deque

que = deque([])

dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]

for i in range(4):
    x = dx[i]
    y = dy[i]
    if 0 <= start[0] + y <= H - 1 and 0 <= start[1] + x <= W - 1:
        tmp = items[start[0] + y][start[1] + x]
        if tmp == ".":
            que.append((start[0] + y, start[1] + x))
            prev[start[0] + y][start[1] + x] = True
k = K
while len(que) != 0:
    q = que.popleft()
    a = q[0]
    b = q[1]
    if abs(start[0] - a) + abs(start[1] - b) > K:
        continue
    c = min(min(a, H - 1 - a), min(b, W - 1 - b))
    if c < diff:
        diff = c
        p = (a, b)

    for i in range(4):
        x = dx[i]
        y = dy[i]
        if 0 <= a + y <= H - 1 and 0 <= b + x <= W - 1:
            if prev[a + y][b + x]:
                continue
            tmp = items[a + y][b + x]
            if tmp == ".":
                que.append((a + y, b + x))
                prev[a + y][b + x] = True

ans = 1
if diff == 0:
    print(ans)
else:
    print(ans + (K - 1 + diff) // K)
### BUGGY CODE ###

N=int(input())
H=[]
for i in range(5):
  H += [int(input())]
X=[N,0,0,0,0,0]#移動前の人数
count=0
goal=0
while goal<N:#6番目の都市の人数がN人以下なら移動を続ける
  count +=1
  Y=[0]*6#移動後の人数
  for i in range(5):
    if X[i]>=H[i]:#一回で乗り切れないとき
      Y[i+1] += H[i]
      Y[i] += X[i]-H[i]
    elif X[i]<H[i]:#全員乗れる
      Y[i+1] +=X[i]
  goal +=Y[5]
  X=Y
print(count)

### FIXED CODE ###

N=int(input())
H=[]
for i in range(5):
  H += [int(input())]
print(-(-N//min(H))+4)
### BUGGY CODE ###

from time import time
import sys
sys.setrecursionlimit(10 ** 9)


def func(v, color):
    if visited[v] != 2:
        return
    visited[v] = color
    for next_v in range(n):
        if graph[v][next_v] != 0:  # vとnext_vが繋がっている場合
            if graph[v][next_v] % 2 == 0:
                func(next_v, color)
            else:
                func(next_v, color ^ 1)


n = int(input())
side = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n-1)]
graph = [[0] * n for _ in range(n)]
visited = [2] * n  # 2は未訪問 0は白 黒は1

for u, v, w in side:
    graph[u-1][v-1] = graph[v-1][u-1] = w

func(0, 0)

for i in visited:
    print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)


def func(v, c):
    for next_v, w in graph[v]:
        if color[next_v] == -1:
            color[next_v] = (c + w) & 1
            func(next_v, c + w) 

n = int(input())
graph = [[] for _ in range(n)]
color = [-1] * n

for _ in range(n-1):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))


color[0] = 0
func(0, 0)

for i in color:
    print(i)
### BUGGY CODE ###

import math
import string
import collections
from collections import Counter


def readints():
    return list(map(int, input().split()))


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


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
# print(a)
ans = 0
# print(a[:0]+a[1:])
for i in range(n):
    ans = max(a[:i]+a[(i+1):])
    print(ans)


### FIXED CODE ###

import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


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


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
b = sorted(a)
max = b[-1]
max_sec = b[-2]

for A in a:
    if A == max:
        print(max_sec)
    else:
        print(max)
### BUGGY CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


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

s1=input()

s2=input()

len_moji = lcm(n,m)

len_s1 = []

len_s2 = []

for i in range(n):
    len_s1.append(i*len_moji//n+1)

for i in range(m):
    len_s2.append(i*len_moji//m+1)
#print(len_s1,len_s2)

for ix, vs1 in enumerate(len_s1):
    for jx, vs2 in enumerate(len_s2):
        if vs1 == vs2:
            if s1[ix] != s2[jx]:
                print(-1)
                exit()
print(len_moji)

### FIXED CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


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

s1=input()

s2=input()

len_moji = lcm(n,m)

len_s1 = []

len_s2 = []

for i in range(n):
    len_s1.append(i*len_moji//n+1)

for i in range(m):
    len_s2.append(i*len_moji//m+1)
#print(len_s1)
#print(len_s2)
count = 0
for ix, vs1 in enumerate(len_s1):
    for jx in range(count,len(len_s2)):
        #print(vs1, len_s2[jx])
        if vs1 < len_s2[jx]:
            count = jx-1
            break
        if vs1 == len_s2[jx]:
            count = jx
            if s1[ix] != s2[jx]:
                print(-1)
                exit()
            break
print(len_moji)
### BUGGY CODE ###

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

for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] == 'R':
            if S[j] == 'R':
                continue
            elif S[j] == 'G':
                if 2*j-i < N:
                    total += S[j+1:2*j-i].count('B')
                    total += S[2*j-i+1:N].count('B')
                else:
                    total += S[j+1:N].count('B')
            elif S[j] == 'B':
                if 2*j-i < N:
                    total += S[j+1:2*j-i].count('G')
                    total += S[2*j-i+1:N].count('G')
                else:
                    total += S[j+1:N].count('G')
        elif S[i] == 'G':
            if S[j] == 'G':
                continue
            elif S[j] == 'B':
                if 2*j-i < N:
                    total += S[j+1:2*j-i].count('R')
                    total += S[2*j-i+1:N].count('R')
                else:
                    total += S[j+1:N].count('R')
            elif S[j] == 'R':
                if 2*j-i < N:
                    total += S[j+1:2*j-i].count('B')
                    total += S[2*j-i+1:N].count('B')
                else:
                    total += S[j+1:N].count('B')
        elif S[i] == 'B':
            if S[j] == 'B':
                continue
            elif S[j] == 'G':
                if 2*j-i < N:
                    total += S[j+1:2*j-i].count('R')
                    total += S[2*j-i+1:N].count('R')
                else:
                    total += S[j+1:N].count('R')
            elif S[j] == 'R':
                if 2*j-i < N:
                    total += S[j+1:2*j-i].count('G')
                    total += S[2*j-i+1:N].count('G')
                else:
                    total += S[j+1:N].count('G')

print(total)


### FIXED CODE ###

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

for i in range(N-2):
    if S[i] == "R":
        num_G = S[i+1:].count('G')
        num_B = S[i+1:].count('B')
        total += num_G * num_B
    elif S[i] == "G":
        num_B = S[i+1:].count('B')
        num_R = S[i+1:].count('R')
        total += num_B * num_R
    elif S[i] == "B":
        num_G = S[i+1:].count('G')
        num_R = S[i+1:].count('R')
        total += num_G * num_R

for i in range(N-2):
    for j in range(i+1, N-1):
        if 2*j-i >= N:
            continue
        if S[j] != S[i] and S[2*j-i] != S[j] and S[2*j-i] != S[i]:
            total -= 1

print(total)
### BUGGY CODE ###

K=int(input())
A=[0]*K
i=0
j=1
while i<K:
    if j<=9:
        A[i]=j
        i+=1
    else:
        j=str(j)
        l=0
        while l+1<=len(j):
            if l+1==len(j):
                A[i]=int(j)
                i+=1
                j=int(j)
                break
            elif int(j[l+1])-1<=int(j[l])<=int(j[l+1])+1:
                l+=1
            else:
                j=int(j)
                break
    j+=1
print(A[K-1])

### FIXED CODE ###

K=int(input())
A=[1,2,3,4,5,6,7,8,9]+[0]*10*K
i=9
j=0
while i<K:
    if A[j]%10!=0 and A[j]%10!=9:
        A[i]=10*A[j]+A[j]%10-1;i+=1
        A[i]=10*A[j]+A[j]%10;i+=1
        A[i]=10*A[j]+A[j]%10+1;i+=1
    elif A[j]%10==0:
        A[i]=10*A[j]+A[j]%10;i+=1
        A[i]=10*A[j]+A[j]%10+1;i+=1
    else:
        A[i]=10*A[j]+A[j]%10-1;i+=1
        A[i]=10*A[j]+A[j]%10;i+=1
    j+=1
print(A[K-1])
### BUGGY CODE ###

def main():
    x,y = map(int,input().split())
    tmp = []
    for i in range(2,max(2,min(int(x // 2)+1, int(y //2 )+1))):
        if x % i ==0 and y % i == 0:
            tmp.append(i)
            while True:
                if x % i == 0:
                    x = x//i
                else:
                    break
            while True:
                if y % i == 0:
                    y = y//i
                else:
                    break


    print(len(tmp) + 1)
    # print(tmp)
    # for i,a in enumerate(tmp):
    #     if a < 4:
    #         tmp[i] = 1
    #         continue
    #     j = 2
    #     for j in range(2,int(a**0.5)+1):
    #         if a % j == 0:
    #             tmp[i] = 0
    #             break
    #     if tmp[i] != 0:
    #         tmp[i] = 1
    # print(sum(tmp))
    # print(tmp)

    # cnt = 0
    # # print(tmp)
    # flg = 0
    # for i,a in enumerate(tmp):
    #     # print('out' + str(i) + ' ' + str(a))
    #     if a == 1:
    #         continue
    #     leng = len(tmp)
    #     for j in range(i+1,leng):
    #         # print(j)
    #         # print(tmp)
    #         # print(leng)
    #         if flg == 1:
    #             j -=1
    #         flg = 0
    #         if j >= leng:
    #             break
    #         # print(str(j) + ' ' + str(leng) + ' ' + str(tmp[j]))
    #         if tmp[j] % a == 0:
    #             tmp.pop(j)
    #             leng -=1
    #             j -= 1
    #             # print(tmp)
    #             # print(j)
    #             flg = 1
    #
    #                 # print(j)
    #                 # print(a)
    #

    # print(len(tmp))
    # print(tmp)
if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    x,y = map(int,input().split())
    tmp = [1]
    i = 2
    ans = 0
    # if x == y:
    #     ans += 1
    # a = factorization(x)
    # print(a)
    tempx = x

    for i in range(2, int(-(-x**0.5//1))+1):
        if tempx % i == 0:
            tmp.append(i)
            while tempx % i == 0:

                tempx //= i
    if tempx!=1:
        tmp.append(tempx)
    # print(tmp)

    for i,a in enumerate(tmp):
        if y % a == 0:
            tmp[i] = 1
        else:
            tmp[i] = 0
    print(sum(tmp))


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

N, M = map(int, input().split())
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
MOD = 10**9 + 7
ns = len(S)
nt = len(T)
dp = [[0] * (nt + 1) for i in range(ns + 1)]
for i in range(1, ns + 1):
    for j in range(1, nt + 1):
        if (S[i - 1] == T[j - 1]):
            dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]
print((dp[ns][nt] + 1) % MOD)

### FIXED CODE ###

N, M = map(int, input().split())
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
MOD = 10**9 + 7
ns = len(S)
nt = len(T)
dp = [[0] * (nt + 1) for i in range(ns + 1)]
for i in range(1, ns + 1):
    for j in range(1, nt + 1):
        if (S[i - 1] == T[j - 1]):
            dp[i][j] = (1 + dp[i][j - 1] + dp[i - 1][j]) % MOD
        else:
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]) %            MOD
print((dp[ns][nt] + 1) % MOD)
### BUGGY CODE ###

n=int(input())
s=input()
dp=[(n+1)*[0]for _ in range(n+1)]
ans=0
for i in range(1,n):
    for j in range(i+1,n+1):
        if s[i-1]==s[j-1]:
            dp[i][j]=min(dp[i-1][j-1]+1,j-i)
            ans=max(ans,dp[i][j])
print(ans)

### FIXED CODE ###

n=int(input())
s=list(map(ord,list(input())))
dp=[n*[0]for _ in range(n)]
for i in range(n):
  if s[i]==s[0]:
    dp[i][0]=dp[0][i]=1
for i in range(1,n):
  for j in range(1,n):
    if s[i]==s[j]:
      dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if i<j-dp[i][j]+1:ans=max(ans,dp[i][j])
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(v) for v in input().split()]

ans = 0

for i in range(1,N+1):
    l = A[i-1]
    for j in range(l+i,N+1):
        r = A[j-1]
        if j - i == l + r: ans += 1
print(ans)


### FIXED CODE ###

from collections import defaultdict

N = int(input())
A = [int(v) for v in input().split()]

ans = 0
dic = defaultdict(int)

for i,a in enumerate(A):
    dic[i-a] += 1

for i,a in enumerate(A):
    ans += dic[a+i]

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

from math import gcd

k = int(input())
ans = 0

for i in range(k):
    for j in range(k):
        for ii in range(k):
            ans += gcd(i+1,gcd(j+1,ii+1))

print(ans)


### FIXED CODE ###

from math import gcd

k = int(input())
ans = 0

for i in range(k):
    for j in range(k):
        for ii in range(k):
            ans += gcd(i+1,gcd(j+1,ii+1))

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

inp = input().split()
n, k = int(inp[0]), int(inp[1])
p = input().split()
p = list(map(int, p))
max_ = 0
for i in range(n-k+1):
  sum_ = 0
  for j in range(k):
    sum_ = sum_ + (p[i+j]+1)/2
  if sum_ > max_:
    max_ = sum_
print(max_)

### FIXED CODE ###

inp = input().split()
n, k = int(inp[0]), int(inp[1])
p = input().split()
p = list(map(int, p))
sum_ = 0
max_ = 0
for i in range(n):
    sum_ += p[i]
    if i >= k:
        sum_ -= p[i-k]
    if sum_ > max_:
        max_ = sum_
print((max_+k)/2)
### BUGGY CODE ###

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

ans = 1
for ai in a:
    ans *= ai

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 1
for ai in a:
    ans *= ai
    if ans == 0:
        print(0)
        break
    elif ans > 10 ** 18:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
a = [input() for _ in range(N)]

cc = [sorted(Counter(x).most_common()) for x in a]
ans = 0
for i in range(N):
  for j in range(i + 1, N):
    if cc[i] == cc[j]:
      ans += 1
      
print(ans)

### FIXED CODE ###

from scipy.special import comb
N = int(input())
a = [input() for _ in range(N)]

d = dict()
for x in a:
  s = ''.join(sorted(x))
  if s not in d.keys():
    d[s] = 1
  else:
    d[s] += 1

print(sum([comb(i, 2, exact=True) for i in d.values()]))
### BUGGY CODE ###

from numpy import*;B=searchsorted;a,b=loadtxt(open(0),skiprows=1);c=0;l=2**29
while l:h=l;l//=2;y=sort(hstack((b%h-h,b%h)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

### FIXED CODE ###

from numpy import*;B,I=searchsorted,lambda:int32(input().split());input();a,b=I(),I();c=0
for k in range(29):l=2**k;h=l*2;x,y=a%h,sort(b%h);y=hstack((y-h,y));c+=sum(B(y,h-x)-B(y,l-x))%2*l
print(c)