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

import sys

A=[[0,0,0]]
buf=[]
size = 0

def insert(A,x):
    global size,buf
    fp=A[0][1]
    try:
        if buf==[]:
            buf = [i for i,e in enumerate(A) if e==-1]
        else:
            i = buf[-1]
            buf = buf[:-1]
        A[i]=[x,fp,0]
        A[fp][2]=i
        A[0][1]=i
    except:
        A.append([x,fp,0])
        A[fp][2]=len(A)-1
        A[0][1]=len(A)-1     
    size += 1    

def delete(A,x):
    global size
    p =A[0][1]
    while A[p][0]!=x:
        p=A[p][1]
        if p==0: return
    fp=A[p][1]
    bp=A[p][2]
    A[fp][2]=bp
    A[bp][1]=fp
    A[p]=[-1,-1,-1]
    size -= 1
    return

def deletefirst(A):
    global size
    if size == 0: return
    p=A[0][1]
    fp=A[p][1]
    A[0][1]=fp
    A[fp][2]=0
    A[p]=[-1,-1,-1]
    size -= 1
    return 0

def deletelast(A):
    global size
    if size == 0: return
    p=A[0][2]
    bp=A[p][2]
    A[0][2]=bp
    A[bp][1]=0
    A[p]=[-1,-1,-1]
    size -= 1
    return 0

n=int(raw_input())
while n:
    s = (raw_input().split())
    if s[0] == 'insert':
        insert(A,s[1])
    elif s[0] == 'delete':
        delete(A,s[1])
    elif s[0] == 'deleteFirst':
        deletefirst(A)
    elif s[0] == 'deleteLast':
        deletelast(A)
    n -=1
    
e = A[0][1]
while e!=0:
    print A[e][0],
    e = A[e][1]

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
### BUGGY CODE ###

s = int(input())
i = 9
flag = True
while i >= 1:
    if s % i == 0 and s / i <=9:
        print("Yes")
        flag = False
        break
if flag:
    print("No")

### FIXED CODE ###

s = int(input())
i = 9
flag = True
while i >= 1:
    if s % i == 0 and s / i <=9:
        print("Yes")
        flag = False
        break
    i -= 1
if flag:
    print("No")
### BUGGY CODE ###

N=int(input())
hlist=list(map(int,input().split()))
hantei="Yes"
for i in range(1,N):
  for j in range(i):
    if hlist[j]>=hlist[i]+2:
      hantei="No"
print(hantei)

### FIXED CODE ###

N=int(input())
hlist=list(map(int,input().split()))
hantei="Yes"
kabe=0
for i in range(1,N):
  if hantei=="No":
    break
  kabe=max(kabe,hlist[i])
  if kabe>=hlist[i]+2:
    hantei="No"
print(hantei)
### BUGGY CODE ###

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

L=[0]*M
R=[0]*M
for i in range(M):
  L[i], R[i] = map(int, input().split())

keys = []

for i in range(M):
  keys.append(set(range(L[i],R[i]+1)))
  
common = set(range(1, N+1))
for i in range(M):
  common = common & keys[i]
    
print(len(common))

### FIXED CODE ###

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

L=[0]*M
R=[0]*M
for i in range(M):
  L[i], R[i] = map(int, input().split())
    
print(max(min(R)-max(L)+1,0))
### BUGGY CODE ###

import numpy as np

h, w = list(map(int, input().split()))
d = {".":1, "#":0}
ss = np.array([list(input()) for _ in range(h)])
ss = np.array([[d[x] for x in s] for s in ss])

ls, rs, us, ds = [np.zeros((h, w)) for _ in range(4)]

ls[:, 0] = ss[:, 0]
rs[:, w-1] = ss[:, w-1]
us[0, :] = ss[0, :]
ds[h-1, :] = ss[h-1, :]

for i in range(1, w):
	ls[:, i] = ss[:, i] * (ls[:, i - 1] + 1)

for i in reversed(range(w - 1)):
	rs[:, i] = ss[:, i] * (rs[:, i + 1] + 1)

for i in range(1, h):
	us[i, :] = ss[i, :] * (us[i - 1, :] + 1)

for i in reversed(range(h - 1)):
	ds[i, :] = ss[i, :] * (ds[i + 1, :] + 1)

# print(ss)
# print(ls)
# print(rs)
# print(us)
# print(ds)
print(max(int(np.amax(ls + rs + us + ds) - 3), 0))


### FIXED CODE ###

import numpy as np

h, w = list(map(int, input().split()))
d = {".":1, "#":0}
ss = np.array([list(input()) for _ in range(h)]) == "."
ss_t = ss.transpose()

ls, rs, us, ds = [np.zeros((h, w), dtype=int) for _ in range(4)]

ls, rs = ls.transpose(), rs.transpose()

ls[0] = ss_t[0]
rs[w-1] = ss_t[w-1]
us[0] = ss[0]
ds[h-1] = ss[h-1]

for i in range(1, w):
	ls[i] = ss_t[i] * (ls[i - 1] + 1)

for i in reversed(range(w - 1)):
	rs[i] = ss_t[i] * (rs[i + 1] + 1)

for i in range(1, h):
	us[i] = ss[i] * (us[i - 1] + 1)

for i in reversed(range(h - 1)):
	ds[i] = ss[i] * (ds[i + 1] + 1)

# print(ss)
# print(ls)
# print(rs)
# print(us)
# print(ds)
print(max(np.amax((ls.transpose() + rs.transpose() + us + ds) - 3), 0))
### BUGGY CODE ###

def eratosthenes(a):
    data = [i for i in a]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data
    
n=int(input())
a=list(map(int, input().split()))
a.sort()
L=eratosthenes(a)
from collections import Counter
c=Counter(L)
ans=0
for v in c.values():
    if v==1:
        ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter

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

m=a[-1]+1
dp=[True]*m
c=Counter(a)
ans=0
for x in a:
    if dp[x] and c[x]==1:
        ans+=1
    
    for j in range(2*x, m, x):
        dp[j]=False

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

from collections import Counter
import itertools
N = int(input())
A = list(map(int, input().split()))

def choose2(n):
    return len(list(itertools.combinations(range(n), 2)))

counts = Counter(A)
total = 0
for n, count in counts.items(): 
    #初めに、同じ数同士から2つ選んだ時の組み合わせの総和を求める
    combi = choose2(count)
    total += combi 

for i in A:
    #上で求めた組み合わせの総和から、消える数字について1つ減らしたときの組み合わせを減らす
    temp = total - choose2(counts[i])
    temp += choose2(counts[i] - 1) 
    print(temp)

### FIXED CODE ###

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

def choose2(n):
    return n * (n - 1) // 2

counts = Counter(A)
total = 0
for n, count in counts.items(): 
    #初めに、同じ数同士から2つ選んだ時の組み合わせの総和を求める
    combi = choose2(count)
    total += combi 

for i in A:
    #上で求めた組み合わせの総和から、消える数字について1つ減らしたときの組み合わせを減らす
    temp = total - choose2(counts[i])
    temp += choose2(counts[i] - 1) 
    print(temp)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque
import sys


def main():
  ## input
  N,Q = map(int, sys.stdin.readline().rstrip().split())
  STX = []
  for i in range(N):
    s,t,x = map(int, sys.stdin.readline().rstrip().split())
    heappush(STX, (x, s-x, t-x))
  Dn = [int(sys.stdin.readline().rstrip()) for _ in range(Q)]+[10**10]

  ans = []
  while len(STX) > 0:
    x,s,t = heappop(STX)
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      heappush(ans,(Dn[l],x))
      Dn.pop(l)
  for d in Dn:
    heappush(ans,(d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans)>1:
    print(heappop(ans)[1])


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

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

def resolve():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    e = [sum(range(num+1))/float(num) for num in p]
    max_v = float('-inf')
    for i in range(N-K+1):
        exp = sum(e[i:i+K])
        max_v = max(max_v, exp)
    print(max_v)
resolve()

### FIXED CODE ###

def resolve():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    exp_table = [0] * 200002
    curr_sum = 0
    for i in range(1, 200002):
        curr_sum += i
        exp_table[i] = curr_sum / float(i)
    curr_sum = 0
    max_v = float('-inf')
    for i in range(len(p)):
        if i+1 < K:
            curr_sum += exp_table[p[i]]
        elif i+1 == K:
            curr_sum += exp_table[p[i]]
            max_v = max(max_v, curr_sum)
        else:
            curr_sum = curr_sum - exp_table[p[i-K]] + exp_table[p[i]]
            max_v = max(max_v, curr_sum)
        # print(curr_sum, max_v, p[i], exp_table[p[i]])
    print(max_v)
resolve()
### BUGGY CODE ###

#!/usr/bin/env python3
 
import sys

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC138 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
n = len(s)
m = len(t)
f = [False]*26
f2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(n):
    f[alpha.index(s[i])] = True
for i in range(m):
    f2[alpha.index(t[i])] = True
for i in range(26):
    if not f[i] and f2[i]:
        print(-1)
        quit()
ans = 0
inde = s.index(t[0])
ans += inde+1
for i in range(1,m):
    s = s[inde+1:] + s[:inde+1]
    inde = s.index(t[i])
    ans += inde+1
print(ans)
### BUGGY CODE ###

import sys

if __name__ == '__main__':
    n = int(sys.stdin.readline().rstrip())
    A = list(map(lambda x: int(x), sys.stdin.readline().split()))
    q = int(sys.stdin.readline().rstrip())
    B, C = [], []
    for i in range(q):
        b, c = list(map(lambda x: int(x), sys.stdin.readline().split()))
        B.append(b)
        C.append(c)

    dic = {}
    for a in A:
        dic[a] = dic.get(a, 0) + 1

    for i in range(q):
        dic[C[i]] = dic.get(C[i], 0) + dic.get(B[i], 0)
        dic[B[i]] = 0

        summ = 0
        for k, v in dic.items():
            summ += k*v
        print(summ)



### FIXED CODE ###

import sys
import numpy as np

if __name__ == '__main__':
    n = int(sys.stdin.readline().rstrip())
    A = list(map(lambda x: int(x), sys.stdin.readline().split()))
    q = int(sys.stdin.readline().rstrip())
    dic = {}
    for a in A:
        dic[a] = dic.get(a, 0) + 1

    # keys = list(dic.keys())
    # values = list(dic.values())
    # summ = np.array(keys).dot(np.array(values))
    summ = sum([k*v for k, v in dic.items()])
    for i in range(q):
        b, c = list(map(lambda x: int(x), sys.stdin.readline().split()))

        diff = c*dic.get(b,0) - b*dic.get(b,0)
        dic[c] = dic.get(c, 0) + dic.get(b, 0)
        dic[b] = 0
        summ += diff
        print(summ)
### BUGGY CODE ###

from operator import mul
from functools import reduce

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

hyouten_count = N - K

result_list = []

result = 1

for i in range(K-1, N):
    # print(num)
    # result = 1
    num = i-K+1
    result = reduce(mul, A[num:i+1])
    # for j in range(K):
    #     result = result * A[i - j]
    # print(result)
    # print(result)
    result_list.append(result)
    result = 1


for n in range(1, len(result_list)):
    if result_list[n] > result_list[n-1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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


for i in range(K, N): # 3, 5
    if A[i] > A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq
n = int(input())
#n, k = map(int, sys.stdin.readline().split())
s = input()
#a = list(map(int, sys.stdin.readline().split()))

def main():
    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)

    R = len(r)
    G = len(g)
    B = len(b)

    if min(R, G, B) == R:
        if max(R, G, B) == G:
            w = r
            x = b
            y = g
        else:
            w = r
            x = g
            y = b
    elif min(R, G, B) == G:
        if max(R, G, B) == R:
            w = g
            x = b
            y = r
        else:
            w = g
            x = r
            y = b
    else:
        if max(R, G, B) == R:
            w = b
            x = g
            y = r
        else:
            w = b
            x = r
            y = g


    ans = 0
    z = len(y)
    for i in range(len(w)):
        for j in range(len(x)):
            d = abs(w[i] - x[j])
            e = 0
            p = min(w[i], x[j]) - d
            q = max(w[i], x[j]) + d
            if (w[i] + x[j]) % 2 == 0:
                t = int((w[i] + x[j]) / 2)
            else:
                t = 10000
            if p in y:
                e += 1
            if q in y:
                e += 1
            if t in y:
                e += 1

            ans += (z - e)

    print(ans)
            
main()
    


### FIXED CODE ###

import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq
n = int(input())
#n, k = map(int, sys.stdin.readline().split())
s = input()
#a = list(map(int, sys.stdin.readline().split()))

def main():
    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 = 0
    z = len(b)
    for i in range(len(r)):
        for j in range(len(g)):
            d = abs(r[i] - g[j])
            e = 0
            p = min(r[i], g[j]) - d
            q = max(r[i], g[j]) + d
            if (r[i] + g[j]) % 2 == 0:
                t = int((r[i] + g[j]) / 2)
                if p >= 0:
                    if s[p] == "B":
                        e += 1
                if q < n:
                    if s[q] == "B":
                        e += 1
                if s[t] == "B":
                    e += 1
            else:
                if p >= 0:
                    if s[p] == "B":
                        e += 1
                if q < n:
                    if s[q] == "B":
                        e += 1

            ans += (z - e)

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

n,q=map(int,input().split())
s=input()
for i 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()
ans=[0]*n+[0]
for i in range(n):
    if s[i:i+2]=='AC':
        ans[i+1]=ans[i]+1
    else:
        ans[i+1]=ans[i]
for i in range(q):
    l,r=map(int,input().split())
    print(ans[r-1]-ans[l-1])
### BUGGY CODE ###

n,x,y = map(int, input().split())

list =[]
for i in range(n):
  for j in range(i):
    b = i+1
    a = j+1
    if a<=x and b>=y:
      list.append(b-y+x-a+1)
    elif a>x and b>=y:
      d =min(a-x+1,y-a)
      list.append(d+b-y)
    elif a<=x and b<y:
      d =min(b-x,y-b+1)
      list.append(x-a+d)
    elif a>x and b<y:
      list.append(min(b-a,y-b+a-x+1))
    else:
      list.append(b-a)
for i in range(n-1):
  print(list.count(i+1))

### FIXED CODE ###

n,x,y=map(int,input().split())
 
ans=[0]*n
 
list =[]
for i in range(n):
  for j in range(i):
    b = i+1
    a = j+1
    if a<=x and b>=y:
      k =b-y+x-a+1
    elif a>x and b>=y:
      d =min(a-x+1,y-a)
      k =d+b-y
    elif a<=x and b<y:
      d =min(b-x,y-b+1)
      k =x-a+d
    elif a>x and b<y:
      k = min(b-a,y-b+a-x+1)
    ans[k]+=1
    
for i in range(1,n):
  print(ans[i])
### BUGGY CODE ###

import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0))
visited = {}
visited[(cx, cy)] = 0
ans = float("inf")
while q:
    x, y, c = q.popleft()
    if (x, y) in visited and visited[(x, y)] < c:
        continue
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if (nx, ny) in visited and visited[(nx, ny)] < c + 1:
                continue
            visited[(nx, ny)] = c
            if nx == gx and ny == gy:
                continue
            q.appendleft((nx, ny, c))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                # print("warp append")
                if (nx, ny) in visited and visited[(nx, ny)] < c + 1:
                    continue
                visited[(nx, ny)] = c + 1
                if nx == gx and ny == gy:
                    continue
                q.append((nx, ny, c+1))
# print(visited)
if (gx, gy) in visited:
    print(visited[(gx, gy)])
else:
    print(-1)

### FIXED CODE ###

import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e+1)
                    continue
                # print("warp append")
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e+1))

print(-1 if ans == float("inf") else ans)
### BUGGY CODE ###

import itertools

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

minprice = sum(plist)
sumlist =[]
for v in itertools.permutations(plist, K):
  sumlist.append(sum(v))
print (min(sumlist))

### FIXED CODE ###

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

plist.sort()
sum = 0
for i in range(K):
  sum+=plist[i]
print (sum)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

def check(ar):
    b = True
    for i in range(len(ar)):
        if ar[i] % 2 != 0:
            b = False
            break
    return b

answer = 0

for i in range(1000000000):
    if check(a) == True:
        for j in range(len(a)):
            a[j] = int(a[j]/2)
        answer += 1

print(answer)


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

def check(ar):
    b = True
    for i in range(len(ar)):
        if ar[i] % 2 != 0:
            b = False
            break
    return b

answer = 0

for i in range(1000000000):
    if check(a) == True:
        for j in range(len(a)):
            a[j] = int(a[j]/2)
        answer += 1
    else:
        break;

print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
MOD = 10**6+3
q = int(input())

fact = [1]*(MOD+1)
for i in range(1, MOD+1):
    fact[i] = fact[i-1]*i%MOD
finv = [pow(f, MOD-2, MOD) for f in fact]

for _ in range(q):
    x, d, n = map(int, input().split())
    if d == 0:
        ans = pow(x, n, MOD)
    else:
        x_div = x*pow(d, MOD-2, MOD)%MOD
        if x_div+n-1 > MOD:
            ans = 0
        else:

            if x_div+n-1 >= MOD:
                ans = 0
            else:
                ans = fact[x_div+n-1]*finv[x_div-1]%MOD*pow(d, n, MOD)%MOD
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
MOD = 10**6+3
q = int(input())

fact = [1]*(MOD+1)
for i in range(1, MOD+1):
    fact[i] = fact[i-1]*i%MOD

for _ in range(q):
    x, d, n = map(int, input().split())
    if d == 0:
        ans = pow(x, n, MOD)
    else:
        x_div = x*pow(d, MOD-2, MOD)%MOD
        if x_div+n-1 > MOD:
            ans = 0
        else:

            if x_div+n-1 >= MOD:
                ans = 0
            else:
                f = fact[x_div+n-1]
                fi = pow(fact[x_div-1], MOD-2, MOD)
                ans = f*fi%MOD*pow(d, n, MOD)%MOD
    print(ans)
### BUGGY CODE ###

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    dd = defaultdict(list)
    count = 0
    for i in range(N - 1):
        ai = A[i]
        iai = i + ai
        if dd[iai] == []:
            for j in range(i + 1, N):
                if j - A[j] == iai:
                    dd[iai].append(j)
                    count += 1
        else:
            for j in dd[iai]:
                if j > i:
                    count += 1
    print(count)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    b = [0] * (10 ** 6)
    ans = 0
    for i in range(n):
        if i - a[i] > 0:
            ans += b[i - a[i]]
        if i + a[i] < 10 ** 6:
            b[i + a[i]] += 1
    print(ans)


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

import numpy as np
import numba
from numba import jit, njit

@njit
def solve(dp, sn):
    for i in range(n-2, -1, -1):
        for j in range(n-1, i,-1):
            if i + dp[i+1][j+1] >= j:
                break
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j+1] + 1
    return dp.max()

n = int(input())
s = input() + '_'
sn = np.zeros(n+1, dtype=int)
for i in range(n+1):
    sn[i] = ord(s[i])

dp = np.zeros((n+1,n+1), dtype=int)

print(solve(dp, sn))

### FIXED CODE ###

n = int(input())
s = input() + '_'
    
dp = [[0]*(n+1) for i in range(n+1)]
for i in range(n-2, -1, -1):
    for j in range(n-1, i,-1):
        if i + dp[i+1][j+1] >= j:
            break
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
print(max(list(map(lambda x: max(x), dp))))
### BUGGY CODE ###

N = int(input())
lis = list(map(int,input().split()))
l = []
i = 0
x = 0
while(True):
  if i == N-1:
    x += 1
    l.append(x)
    break
  if lis[i] != lis[i+1]:
    x += 1
    l.append(x)
    x = 0
  else:
    x += 1
s = 0
for i in lis:
  s += (i//1)
print(s)

### FIXED CODE ###

N = int(input())
lis = list(map(int,input().split()))
l = []
i = 0
x = 0
while(True):
  if i == N-1:
    x += 1
    l.append(x)
    break
  if lis[i] != lis[i+1]:
    x += 1
    l.append(x)
    x = 0
  else:
    x += 1
  i += 1
s = 0
for i in l:
  s += (i//2)
print(s)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = N
for a in P:
    for b in P[:P.index(a)+1]:
        if a > b:
            cnt -=1
            break
print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 0
max = 2*10**5
for a in P:
    if a <=max:
        #print(a)
        cnt += 1
    max = min(max,a)
print(cnt)