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

import time
# start = time.time()
import sys
# sys.stdin = open('input.txt')

from math import gcd


n = int(input())
s = input()
i_indices = []
j_indices = []
k_indices = []

for i in range(n):
    if s[i] == 'R':
        i_indices.append(i+1)
    elif s[i] == 'G':
        j_indices.append(i+1)
    else:
        k_indices.append(i+1)

# print(i_indices, len(i_indices))
# print(j_indices, len(j_indices))
# print(k_indices, len(k_indices))

ans = 0

for i in i_indices:
    for j in j_indices:
        for k in k_indices:
            tmp  = [i, j, k]
            tmp.sort()
            if tmp[1] - tmp[0] != tmp[2] - tmp[1]:
                ans += 1
print(ans)
# end = time.time()
# print(end - start)

### FIXED CODE ###

import time
start = time.time()
import sys
# sys.stdin = open('input.txt')

n = int(input())
s = input()
# 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 = s.count('R') * s.count('G') * s.count('B')
# print(ans)

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

print(ans)
# end = time.time()
# print(end - start)
### BUGGY CODE ###

n,m=map(int,input().split())
ans=1
for i in range(2,(m//n+1)):
  if m%i==0:
    if m//i>=n:
      ans=i
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
ans=1
for i in range(1,int(m**0.5)+1):
  if m%i==0:
    y=m//i
    if m//i>=n and ans<i:
      ans=i
    if m//y>=n and ans<y:
      ans=y
print(ans)
### BUGGY CODE ###

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

l = 0
r = max(A)
m = (r + l) // 2

def cal(N, T, A):
    return max([A[i] - min(A[:i]) for i in range(1,len(A))]) * T // 2

ans = 0
m = cal(N, T, A)
for i in range(1, N):
    if m == (A[i] - min(A[:i])) * T // 2:
        ans += 1
print(ans)



### FIXED CODE ###

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


m = 0
_mini = A[0]
for i in range(1, N):
    _mini = min((_mini, A[i]))
    m = max((m, A[i] - _mini))

ans = 0
mini = A[0]
for i in range(1, N):
    mini = min((mini, A[i]))
    if m == (A[i] - mini):
        ans += 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    for k in range(30, -1, -1):
        if pow2[k] - a[i] != a[i]:
            if d[pow2[k] - a[i]] > 0 and d[a[i]] > 0:
                p = min(d[pow2[k] - a[i]], d[a[i]])
                num += p
                d[pow2[k] - a[i]] -= p
                d[a[i]] -= p
                break
        else:
            if d[a[i]] >= 2:
                num += d[a[i]] // 2
                d[a[i]] %= 2
                break
print(num)

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    if d[a[i]] == 0:
        continue
    for k in range(30, -1, -1):
        inv = pow2[k] - a[i]
        if inv < 0 or inv > a[i]:
            continue
        if inv != a[i]:
            if d[inv] > 0 and d[a[i]] > 0:
                p = min(d[inv], d[a[i]])
                num += p
                d[inv] -= p
                d[a[i]] -= p
                break
        else:
            if d[a[i]] >= 2:
                num += d[a[i]] // 2
                d[a[i]] %= 2
                break
print(num)
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted([int(x) for x in input().split()])

for i in range(M):
    A[-1] = A[-1]//2
    A.sort()
print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [-int(x) for x in input().split()]

heapq.heapify(A)
for i in range(M):
    heapq.heappush(A,-(-heapq.heappop(A)//2))
                   
print(-sum(A))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K=int(input())

i=1
j=1
k=1
r=0
list=[2,3,5,7,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]

while(i<K+1):
  j=1
  f=0
  if(i in list == True):
    f=1
  while(j<K+1):
    k=1
    g=0
    if(j in list == True):
      g=1
    while(k<K+1):
      h=0
      if(k in list == True):
        h=1
      if(i==1 or j==1 or k==1):
        r+=1
      elif(f==1 or g==1 or h==1):
        r+=1
      elif(f==1 and g==1 and h==1):
        if(i==j and j==k):
          r+=i
        else:
          r+=1
      else:
        r+=gcd(i, j, k)
      k+=1
    j+=1
  i+=1

print(r)

### FIXED CODE ###

import math

K=int(input())
r=0

for i in range(1,K+1):
  for j in range(1,K+1):
    a=math.gcd(i,j)
    for k in range(1,K+1):
      b=math.gcd(a,k)
      r+=b
print(r)
### BUGGY CODE ###

def solve():
    mod=998244353
    N=int(input())
    A=[]
    for i in range(N):
        A.append(int(input()))
    su=sum(A)
    su2=su//2
    A.sort()
    csum=[0]*(N+1)
    for i in range(N):
        csum[i+1]=csum[i]+A[i]

    q=[]
    q.append((N-2,0,0,A[N-1]))
    b=[0]*3
    ans=0
    try:
        while True:
            i,b[0],b[1],b[2] = q.pop()
            b.sort()
            if i==0:
                if b[0]+b[1]+A[0]>b[2] and b[1]+b[2]>b[0]+A[0]:
                    ans+=1
                if b[0]+b[1]+A[0]>b[2] and b[0]+b[2]>b[1]+A[0]:
                    ans+=1
                if b[0]+b[1]>b[2]+A[0]:
                    ans+=1
                continue
            if i>=N-3:
                q.append((i-1,b[0],b[1],b[2]+A[i]))
                q.append((i-1,b[0],b[1]+A[i],b[2]))
                q.append((i-1,b[0]+A[i],b[1],b[2]))
                continue
            if b[0]+b[1]>b[2]+csum[i+1]:
                ans+=3**(i+1)
                ans%=mod
                continue
            if b[0]+b[1]+csum[i+1]<=b[2]:
                continue
            q.append((i-1,b[0],b[1],b[2]+A[i]))
            q.append((i-1,b[0],b[1]+A[i],b[2]))
            q.append((i-1,b[0]+A[i],b[1],b[2]))
    except IndexError:
        pass
    ans*=3
    ans%=mod
    return ans

print(solve())


### FIXED CODE ###

def solve():
    mod=998244353
    N=int(input())
    A=[]
    for i in range(N):
        A.append(int(input()))
    sumA=sum(A)
    sumA2=(sumA+1)//2

    dp = [[0]*(sumA2+2) for i in range(N+1)]
    dp[0][0]=1
    for i in range(N):
        for j in range(sumA2+1):
            if dp[i][j]!=0:
                dp[i+1][j]=(dp[i+1][j]+dp[i][j]*2)%mod
                j2=min(sumA2,j+A[i])
                dp[i+1][j2]=(dp[i+1][j2]+dp[i][j])%mod
    ans=1
    for i in range(N):
        ans=(ans*3)%mod
    ans=(ans+mod-3*dp[N][sumA2])%mod

    if sumA%2==0:
        dp = [[0]*(sumA2+2) for i in range(N+1)]
        dp[0][0]=1
        for i in range(N):
            for j in range(sumA2+2):
                if dp[i][j]!=0:
                    dp[i+1][j]+=dp[i][j]
                    j2=min(sumA2+1,j+A[i])
                    dp[i+1][j2]+=dp[i][j]
        ans=(ans+3*dp[N][sumA2])%mod

    return ans

print(solve())
### BUGGY CODE ###

s = input()
t = input()

p = 0
roop = 0
dic = [['' for i in range(len(s))] for j in range(26)]

for i in range(len(t)):
    dis = 0
    if dic[ord(t[i])-97][p] == '':
        for j in range(p,len(s)):
            if t[i] == s[j]:
                for k in range(p,j+1):
                    dic[ord(t[i])-97][k] = j
                dis = 1
                break
        if dis == 0:
            for j in range(0,p):
                if t[i] == s[j]:
                    for k in range(p,len(s)):
                        dic[ord(t[i])-97][k] = j
                    for k in range(0,j+1):
                        dic[ord(t[i])-97][k] = j
                    dis = 1
                    break
        if dis == 0:
            dis = 2
            break
    if p > dic[ord(t[i])-97][p]:
        roop += 1
    if dic[ord(t[i])-97][p] == len(s)-1:
        roop += 1        
        p = 0
    else:
        p = dic[ord(t[i])-97][p] + 1

if dis == 2:
    print(-1)
else:
    print(roop*len(s)+p)

### FIXED CODE ###

s = input()
t = input()

p = 0
roop = 0
dic = [['' for i in range(len(s))] for j in range(26)]

for i in range(len(t)):
    dis = 0
    if dic[ord(t[i])-97][p] == '':
        for j in range(p,len(s)):
            if t[i] == s[j]:
                for k in range(p,j+1):
                    dic[ord(t[i])-97][k] = j
                dis = 1
                break
        if dis == 0:
            for j in range(0,p):
                if t[i] == s[j]:
                    for k in range(p,len(s)):
                        dic[ord(t[i])-97][k] = j
                    for k in range(0,j+1):
                        dic[ord(t[i])-97][k] = j
                    dis = 1
                    break
        if dis == 0:
            dis = 2
            break
    if p > dic[ord(t[i])-97][p]:
        roop += 1
    if dic[ord(t[i])-97][p] == len(s)-1:
        roop += 1        
        p = 0
    else:
        p = dic[ord(t[i])-97][p] + 1

if dis == 2:
    print(-1)
else:
    print(roop*len(s)+p)
### BUGGY CODE ###

n,k = [int(x) for x in input().split()]
p = tuple(int(x) for x in input().split())


def kitaichi(num):
    return (sum(range(num+1)) / num)


tmp = 0
tmp_i = 0
for i in range(n-k+1):
    a = sum(tuple(p[x] for x in range(i, i+k)))
    if a > tmp:
        tmp = a
        tmp_i = i

ans = tuple(kitaichi(p[tmp_i+x]) for x in range(k))
print(sum(ans))

### FIXED CODE ###

n,k = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]


t = [0] * (n+k+1)
for i in range(n):
    t[i+1] = t[i] + p[i]

ans = 0
for i in range(n):
    ans = max(ans, t[i+k]-t[i])
print((ans+k)/2)
### BUGGY CODE ###

import math
k = int(input())
s = input()

ss = len(s)

mod = 10**9 + 7

m25 = []
m26 = []
a = 1
b = 1

for i in range(k+1):
    m25.append(a)
    a *= 25
    a %= mod

for i in range(k+1):
    m26.append(b)
    b *= 26
    b %= mod

samu = 0
for i in range(k+1):
    sm = math.factorial(ss+k-i-1) // (math.factorial(ss-1) * math.factorial(k-i))
    sm %= mod
    sm *= m25[k-i]
    sm *= m26[i]
    sm %= mod
    samu += sm

samu %= mod
print(samu)

### FIXED CODE ###

import math
k = int(input())
s = len(input())

mod = 10**9 + 7

m25 = [] # 25の階乗をmodで割ったあまりを記録する配列
m26 = [] # 26の階乗
m_n = [1] # 逆元を記録する
a = 1
b = 1

for i in range(k+1):
    m25.append(a)
    a *= 25
    a %= mod

for i in range(k+1):
    m26.append(b)
    b *= 26
    b %= mod

for i in range(2,k+s):
    x = mod % i
    y = mod // i
    c = - m_n[x-1] * y
    c %= mod
    m_n.append(c)

samu = 0
fc = 1
for i in range(k):
    sm = fc
    sm *= m25[i]
    sm *= m26[k-i]
    sm %= mod
    samu += sm

    fc *= (s + i)
    fc %= mod
    fc *= m_n[i]
    fc %= mod

sm = fc
sm *= m25[k]
sm %= mod
samu += sm

samu %= mod
print(samu)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    BN = 64
    B = [[0] * BN for _ in range(N+1)]
    for i, a in enumerate(A):
        for j in range(BN):
            B[i+1][j] = B[i][j] + ((a >> j) & 1)
    ans = 0
    for i in range(BN):
        b = 1 << i
        for j, a in enumerate(A):
            n = B[N][i] - B[j+1][i]
            if a & b:
                n = N - j  - n - 1
            ans = (ans + b * n % MOD) % MOD
    return ans


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    BN = 64
    B = [[0] * BN for _ in range(N+1)]
    for i, a in enumerate(A):
        for j in range(BN):
            B[i+1][j] = B[i][j] + ((a >> j) & 1)
    ans = 0
    for i in range(BN):
        b = 1 << i
        for j, a in enumerate(A):
            n = B[N][i] - B[j+1][i]
            if a & b:
                n = N - j  - n - 1
            ans = (ans + b * n % MOD) % MOD
    return ans


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

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

from queue import Queue

#入力
H, W = map(int, input().split())

lst = []
for i in range(H):
    lst += [list(input())]

count = 0 #白色のマスの総数
for i in range(H):
    for j in range(W):
        if lst[i][j] == '.':
            count += 1

sx, sy = 1, 1 #スタート位置
gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs(x, y):
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(x)
    q.put(y)
    d[x][y] = 0

    while True:
        px = q.get()
        py = q.get()
        if px == gx-1 and py == gy-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[gx-1][gy-1]

a = bfs(sx-1, sy-1)

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

### FIXED CODE ###

from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

#sx, sy = 1, 1 #スタート位置
#gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(0)
    q.put(0)
    d[0][0] = 0

    while True:
        if q.empty():
            break
        else:
            px = q.get()
            py = q.get()
            if px == H-1 and py == W-1:
                break
            else:
                for dx, dy in move:
                    nx = px + dx
                    ny = py + dy

                    if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                        q.put(nx)
                        q.put(ny)
                        d[nx][ny] = d[px][py] + 1
    return d[H-1][W-1]

a = bfs()

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]

cnt = 0

def is_symmetry(s_):
    for k in range(n):
        for l in range(n):
            if s_[k][l] != s_[l][k]:
                return False
    return True

for i in range(n):
    i_ = (n+i)%n
    s_ = s[i_:] + s[:i_]
    if is_symmetry(s_):
        cnt += 1

print(cnt*n)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]

cnt = 0

def is_symmetry(s_):
    for k in range(n):
        for l in range(k+1, n):
            if s_[k][l] != s_[l][k]:
                return False
    return True

for i in range(n):
    i_ = (n+i)%n
    s_ = s[i_:] + s[:i_]
    if is_symmetry(s_):
        cnt += 1

print(cnt*n)
### BUGGY CODE ###

x=int(input())
a=0
b=0
for i in range(-x,x):
  for j in range(-x,x):
    if i**5-j**5==x:
      a=i
      b=j
      break
  if a!=0:
    break
print(a,b)

### FIXED CODE ###

x=int(input())
a=0
b=0
for i in range(-500,500):
  for j in range(-500,500):
    if i**5-j**5==x:
      a=i
      b=j
      break
  else:
    continue
  break
print(a,b)
### BUGGY CODE ###

N=int(input())

ans=[0]*N

for i in range(1,N):
    for j in range(1,N):
        for k in range(1,N):
            if i**2+j**2+k**2+i*j+j*k+k*i <=N:
                ans[i**2+j**2+k**2+i*j+j*k+k*i-1] +=1

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

### FIXED CODE ###

N=int(input())

ans=[0]*N

for i in range(1,int(N**0.5)):
    if i**2 >=N:
        break
    for j in range(1,int(N**0.5)):
            if i**2+j**2+i*j>=N:
                break
            for k in range(1,int(N**0.5)):
                    if i**2+j**2+k**2+i*j+j*k+k*i <=N:
                        ans[i**2+j**2+k**2+i*j+j*k+k*i-1] +=1

for i in range(N):
    print(ans[i])
### BUGGY CODE ###

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

m = a*b
lst = []
for i in range(1, b+1):
  if m < a*i:
    break
  lst.append(a*i)

for j in range(1, a+1):
  if j*b in lst:
    print(j*b)
    break

### FIXED CODE ###

a, b = map(int, input().split())
aa = []
bb = []

count = 2

while True:
  if a == 1:
    aa.append(a)
    break
  if a%count == 0:
    aa.append(count)
    a = a//count
  else:
      count += 1
    
count = 2

while True:
  if b == 1:
    bb.append(b)
    break
  if b%count == 0:
    bb.append(count)
    b = b//count
  else:
      count += 1
answer = 1
c = set(aa) | set(bb)
for i in c:
  answer *= i ** max(aa.count(i), bb.count(i))
print(answer)
### BUGGY CODE ###

def gcd(a,b):
    if b<a:a,b=b,a
    r=b%a
    return a if r==0else gcd(a,r)
k=int(input())+1
print(sum(gcd(c,gcd(a,b))for a in range(1,k)for b in range(1,k)for c in range(1,k)))

### FIXED CODE ###

from math import*
r=range(1,int(input())+1)
print(sum(gcd(gcd(a,b),c)for a in r for b in r for c in r))
### BUGGY CODE ###

#ABC065

n = int(input())
a = [int(input()) for _ in range(n)]
b = []
count = 0
i = 1
while i != 2:
    if i in b:
        print(-1)
        count = 0
        break
        
    b.append(i)
    i = a[i-1]
    count += 1
    
        
if count != 0:
    print(count)

### FIXED CODE ###

#ABC065

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

i = 1
for _ in range(n):
    
    b.append(i)
    i = a[i-1]
    
    
        
if 2 in b:
    print(b.index(2))
else:
    print(-1)
### BUGGY CODE ###

import sys
############
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def main():
    X = int(input())
    divs = make_divisors(X)
    for d in divs:
        if (X-pow(d,5))%10!=0:
            continue
        for i in range(-d,X):
            Y=pow(i+d,5)-pow(i,5)
            if Y==X:
                print(i+d,i)
                sys.exit()
            elif Y>X and i>0:
                break

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

import sys

def main():
    X = int(input())
    for a in range(-200, 200):
        a5 = pow(a,5)
        for b in range(-200, 200):
            b5 = pow(b,5)
            if a5-b5 == X:
                print(a,b)
                sys.exit()

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

n = int(input())

a, b = [], []
for _ in range(n):
    ta, tb = map(int, input().split())
    a.append(ta)
    b.append(tb)

ans = 0
i = n - 1
while i >= 0:
    r = a[i] % b[i]
    if r != 0:
        t = b[i] - r
        ans += t
        for j in range(i):
            a[j] += t
    i -= 1

print(ans)

### FIXED CODE ###

n = int(input())

a, b = [], []
for _ in range(n):
    ta, tb = map(int, input().split())
    a.append(ta)
    b.append(tb)

ans = 0
i = n - 1
while i >= 0:
    a[i] += ans
    r = a[i] % b[i]
    if r != 0:
        ans += b[i] - r
    i -= 1

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

from collections import deque
N,K= map(int,(input().split()))
p = list(map(int,input().split()))

temp_p = deque([]) 
for i in range(K):
  temp_p.append(p[i])
  sum_m=sum(temp_p)
for j in range(K,N):

  temp_p.popleft()
  temp_p.append(p[j])
  #print(temp_p)
  if(sum(temp_p)>sum_m):
    sum_m=sum(temp_p)
ans=(sum_m/2)+(0.5*K)
print(ans)

### FIXED CODE ###

N,K= map(int,(input().split()))
p = list(map(int,input().split()))
rui_p=[]
rui_p.append(0)
sum_p=[]
for i in range(N):
  rui_p.append(rui_p[i]+p[i])
for j in range(K,N+1):
  sum_p.append(rui_p[j]-rui_p[j-K])

msp=max(sum_p)
ans=(msp/2)+(0.5*K)
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(n):
    if A[i] <= 2*10**5-i:
        a = A[i]
        ato = i+a
        if i+a > n:
            ato = n
        for j in range(ato,n):
            if j-i == A[i]+A[j]:
                ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
X = dict()
ans = 0
for i in range(N):
    L = i + A[i]
    if L not in X:
        X[L] = 1
    else:
        X[L] += 1

for j in range(N):
    R = j - A[j]
    if R in X:
        ans += X[R]

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

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

ans=[0]*(h+1)
for i in range(1,h+1):
    li = [ans[max(i-j[0],0)]+j[1] for j in ab]
    ans[i]=min(li)

print(ans[h])

### FIXED CODE ###

from sys import stdin
h,n=[int(x) for x in stdin.readline().rstrip().split()]
ab=[]
for i in range(n):
    ab.append([int(x) for x in stdin.readline().rstrip().split()])

ans=[0]*(h+1)
for i in range(1,h+1):
    li = [ans[max(i-j[0],0)]+j[1] for j in ab]
    ans[i]=min(li)

print(ans[h])
### BUGGY CODE ###

import numpy as np

a, b, c, k = map(int, input().split())

ones = [1 for i in range(a)]
zeros = [0 for i in range(b)]
minusOnes = [-1 for i in range(c)]

combination = np.array(ones + zeros + minusOnes)
sum = 0
for i in range(k):
    sum += combination[i]
print(sum)


### FIXED CODE ###

a, b, c, k = map(int, input().split())

if k <= a:
    sum = k * 1
elif a < k and k <= a + b:
    sum = a
elif a + b < k <= a + b + c:
    sum = a + (-1) * (k - a - b)

print(sum)
### BUGGY CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
lenL = len(L)
ans = 0
for i in range(lenL-2):
    for j in range(i+1, lenL-1):
        a = L[i]
        b = L[j]
        ind = bisect.bisect_left(L[j+1:], a+b)
        ans += ind
print(ans)



### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
lenL = len(L)
ans = 0
for i in range(lenL-2):
    for j in range(i+1, lenL-1):
        a = L[i]
        b = L[j]
        ind = bisect.bisect_left(L[j+1:], a+b)
        ans += ind
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
p = [list(map(int, input().split())) for i in range(m)]
l = []
for i in range(m):
    l.append([i])
for i in range(m):
    l[i].append(p[i][1])
p.sort(key=lambda x: x[1])
cnt = [0 for i in range(n+1)]
for i in range(m):
    cnt[p[i][0]] += 1
    for j in range(m):
        if p[i][1] == l[j][1]:
            l[j].append(str(p[i][0]).zfill(6)+str(cnt[p[i][0]]).zfill(6))
            break
for i in range(m):
    print(l[i][2])

### FIXED CODE ###

import copy
n, m = map(int, input().split())
p = [list(map(int, input().split())) for i in range(m)]
dic = {}
q = copy.copy(p)
q.sort(key=lambda x: x[1])
cnt = [0 for i in range(n+1)]
for i in range(m):
    cnt[q[i][0]] += 1
    dic[q[i][1]] = cnt[q[i][0]]
for i in range(m):
    print(str(p[i][0]).zfill(6)+str(dic[p[i][1]]).zfill(6))