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

n = int(input())
s = input()
ans = 0
flag = False
for i in range(1000):
    a = i % 10
    b = i // 10 % 10
    c = i // 100 % 10
    for j in range(n):
        if int(s[j]) == c:
            for k in range(j + 1, n):
                if int(s[k]) == b:
                    for l in range(k + 1, n):
                        if int(s[l]) == a:
                            ans += 1
                            flag = True
                            break
                if flag:
                    break
        if flag:
            flag = False
            break
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
password = [0, 0, 0]
for i in range(1000):
    for j in range(3):
        password[2 - j] = i // (10 ** j) % 10
    if str(password[0]) in s:
        index = s.index(str(password[0]))
        if str(password[1]) in s[index + 1:]:
            index2 = index + 1 + s[index + 1:].index(str(password[1]))
            if str(password[2]) in s[index2 + 1:]:
                ans += 1
print(ans)
### BUGGY CODE ###

import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

mod=1000000007
n=int(input())
ans=1
for i in range(1,n+1):
    ans*=i%mod
print(ans%mod)

### FIXED CODE ###

import math
n=int(input())
print(math.factorial(n)%1000000007)
### BUGGY CODE ###

count = 1
while True:
    try:
        n = int(raw_input())
        for i in range(3, n+1):
            #print i
            for j in range(2, i):
                if i == j+1:
                    count += 1
                    #print i
                    #print 111
                    break
                elif i % j ==0:
                    #print 222
                    break
                else:
                    #print 333
                    continue
            #count += 1
            #print 99999999
    except:
        break

print count

### FIXED CODE ###

n=1000000
pr = [1] * n
pr[0],pr[1]=0,0
for i in range(2, int(n**0.5)+1):
    if pr[i] == 1:
        for j in range(i ** 2, n , i):
                pr[j] =0
for k in range(3, n):
    pr[k] += pr[k-1]
while True:
    try:
        m = int(raw_input())
        print pr[m]
    except:
        break
### BUGGY CODE ###

from itertools import product

X,Y,Z,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

BC = [i+j for i,j in product(B,C)]
BC.sort(reverse=True)

ans = [i+j for i,j in product(BC[:min(3000, X*Y*Z)], A)]
ans.sort(reverse=True)

[print(ans[i]) for i in range(K)]


### FIXED CODE ###

from itertools import product

X,Y,Z,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

BC = [i+j for i,j in list(product(B,C))]
BC.sort(reverse=True)

ans = [i+j for i,j in list(product(BC[:min(3000, X*Y*Z)], A))]
ans.sort(reverse=True)

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

def main():
    n, k = list(map(int, input().split()))
    S = list(input())
    T = []
    a, c = S[0], 0
    for s in S:
        if s == a:
            c += 1
        else:
            T.append([a, c])
            a = s
            c = 1
    T.append([a, c])
    ans = 0
    for i, t in enumerate(T):
        if t[0] == '0':
            r = i + 2 * k - 1
        else:
            r = i + 2 * k
        ans = max(ans, sum([a[1] for a in T[i:min(len(T) - 1, r) + 1]]))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
def main():
    n, k = list(map(int, input().split()))
    S = list(input())
    T = []
    V = []
    a, c = S[0], 0
    for s in S:
        if s == a:
            c += 1
        else:
            T.append(a)
            V.append(c)
            a = s
            c = 1
    T.append(a)
    V.append(c)

    V = np.cumsum(np.array(V))
    max_v = len(V)
    ans = 0
    for i, t in enumerate(np.array(T)):
        if t == '0':
            r = i + 2 * k - 1
        else:
            r = i + 2 * k
        if i == 0:
            ans = max(ans, V[min(max_v - 1, r)])
        else:
            ans = max(ans, V[min(max_v - 1, r)] - V[i - 1])
    print(ans)


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

n,m=map(int,input().split())
prev=[];ord=[[]for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  prev.append([a,b])
  ord[a].append(b)
for i in range(n+1):
  if i!=[]:ord[i]=sorted(ord[i])
for [x,y] in prev:
  ind=ord[x].index(y)+1
  print("%06d"%x+"%06d"%ind)

### FIXED CODE ###

n,m=map(int,input().split());li=[]
for i in range(m):
  li.append(list(map(int,input().split()))+[i])
li.sort()
cac=li[0][0];o=2
li[0][1]=1
for g in li[1:]:
  if g[0]!=cac:
    cac=g[0]
    o=1
  g[1]=o
  o+=1
li.sort(key=lambda x:x[-1])
for g in li:
  print("%06d"%g[0]+"%06d"%g[1])
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0]*n
dp[0]=0
for i in range(1,n):
    x=l[i]
    dp[i]=min([dp[j]+abs(x-l[j]) for j in range(max(0,i-k),i)])
print(dp[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int, input().split()))
v=[0]*n
for i in range(1,n):
	u = h[i]
	v[i] = min([v[j] + abs(h[j]-u) for j in range(max(0, i-k), i)])
print(v[n-1])
### BUGGY CODE ###

import queue
import sys
input = sys.stdin.readline

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

ans = [0]*n
checked = [0]*n
checked[0] = 1
for i in range(q):
    p, q = map(int, input().split())
    ans[p-1] += q

ans_q = queue.Queue()
ans_q.put((0, ans[0]))

while not ans_q.empty():
    start = ans_q.get()
    cost = start[1]
    ans[start[0]] = cost
    for e in edge[start[0]]:
        if checked[e] == 0:
            checked[e] = 1
            ans_q.put((e, cost+ans[e]))

for i in range(n):
    print(ans[i], end=' ')
print()


### FIXED CODE ###

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

def main():
    n, q = map(int, input().split())
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

    ans = [0]*n
    checked = [0]*n
    checked[0] = 1
    for i in range(q):
        p, q = map(int, input().split())
        ans[p-1] += q

    ans_q = deque([(0, ans[0])])
    while len(ans_q) > 0:
        start = ans_q.popleft()
        cost = start[1]
        ans[start[0]] = cost
        for e in edge[start[0]]:
            if checked[e] == 0:
                checked[e] = 1
                ans_q.append((e, cost+ans[e]))

    for i in range(n):
        print(ans[i], end=' ')
    print()

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

n=int(input())
a=list(map(int,input().split()))
x=[0]*len(a)

for i in range(n):
  for j in range(n):
    if i==j:
      continue
    if a[i]%a[j]==0:
      x[i]+=1
print(x.count(0))

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
c=Counter(a)
s=list(set(a))
p=[True]*(10**6+1)

for x in s:
    t=x*2
    while t<=10**6:
        p[t]=False
        t+=x
ans=0
for x in a:
    if c[x]==1 and p[x]==True:
        ans+=1
print(ans)
### BUGGY CODE ###

import sys
import math
import copy
input = sys.stdin.readline

N=int(input())
A=[int(input()) for i in range(N)]
SUM=sum(A)
MIN=math.ceil(SUM/3)
MAX=(SUM-1)//2

mod=998244353
from collections import Counter

NALL=Counter()
NALL[(0,0)]=1

ANS=0

for a in A:
    ALL=copy.deepcopy(NALL)
    for l,x in ALL:
        NALL[a+l,x+1]+=ALL[l,x]

    #print(NALL)

ANS=(pow(3,N,mod)-3*pow(2,N,mod))%mod
MINUS=0
for a,x in NALL:
    if MAX<a and N-x>=2:
        MINUS+=3*(pow(2,(N-x),mod)-2)*NALL[a,x]

print((ANS-MINUS+3)%mod)
    


### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=[int(input()) for i in range(N)]
SUM=sum(A)
MAX=(SUM-1)//2

mod=998244353

DPLIST=[0]*(MAX+2)
DPLIST[0]=1

for a in A:
    for i in range(MAX+1,-1,-1):
        if i==MAX+1:
            DPLIST[i]=DPLIST[i]*3%mod
        else:
            DPLIST[min(i+a,MAX+1)]=(DPLIST[min(i+a,MAX+1)]+DPLIST[i])%mod
            DPLIST[i]=DPLIST[i]*2%mod

if SUM%2==1:
    print((sum(DPLIST)-DPLIST[-1]*3)%mod)
    sys.exit()

MAX=SUM//2
       
DPLIST2=[0]*(MAX+2)
DPLIST2[0]=1

for a in A:
    for i in range(MAX+1,-1,-1):
        DPLIST2[min(i+a,MAX+1)]=(DPLIST2[min(i+a,MAX+1)]+DPLIST2[i])%mod

        
print((sum(DPLIST)-DPLIST[-1]*3+DPLIST2[-2]*3)%mod)
### BUGGY CODE ###

a,b,c=map(int,input().split())
if a%2!=0 or b%2!=0 or c%2!=0:
    print(0)
else:
    a1=0
    a2=0
    a3=0
    c1=0
    c2=0
    c3=0
    ans=0
    for i in range(10**9):
        if a%2!=0:
            c1=1        
        if b%2!=0:
            c2=1        
        if c%2!=0:
            c3=1
        if c1==1 or c3==1 or c2==1:
            ans=i
            break
        else:
            a3=(a+b)//2
            a2=(a+c)//2
            a1=(b+c)//2
            a=a1
            b=a2
            c=a3
        #print(a,b,c)
        if i==199999:
            ans=-1
    print(ans)

### FIXED CODE ###

a,b,c=map(int,input().split())
if a%2!=0 or b%2!=0 or c%2!=0:
    print(0)
else:
    a1=0
    a2=0
    a3=0
    c1=0
    c2=0
    c3=0
    ans=0
    for i in range(2*10**5):
        if a%2!=0:
            c1=1        
        if b%2!=0:
            c2=1        
        if c%2!=0:
            c3=1
        if c1==1 or c3==1 or c2==1:
            ans=i
            break
        else:
            a3=(a+b)//2
            a2=(a+c)//2
            a1=(b+c)//2
            a=a1
            b=a2
            c=a3
        #print(a,b,c)
        if i==199999:
            ans=-1
    print(ans)
### BUGGY CODE ###

def resolve():

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

    for i in range(2 ** n):

        new_h = []

        for j in range(n):

            if i >> j & 1:
                new_h.append(h[j] - 1)
            else:
                new_h.append(h[j])

        flg = 0
        for k in range(n-1):
            if new_h[k] > new_h[k+1]:
                flg = 1

        if flg == 0:
            print('Yes')
            return

    print('No')
    
resolve()

### FIXED CODE ###

def resolve():

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

    for i in range(n):

        if i == 0:
            h[i] -= 1
            continue

        if h[i-1] < h[i]:
            h[i] -= 1

        if h[i-1] > h[i]:
            print('No')
            return

    print('Yes')
    
resolve()
### BUGGY CODE ###

n, m = list(map(int, input().split()))
MOD = 10**9+7
dp = [[0 for i in range(2010)] for i in range(2010)]
for i in range(2010):
  dp[i][0] = 1
  dp[0][i] = 1
s = list(map(int, input().split()))
t = list(map(int, input().split()))
for i in range(1, n+1):
  for j in range(1, m+1):
    dp[i][j] = (dp[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1])%MOD
    if s[i-1]==t[j-1]:
      dp[i][j] = (dp[i][j]+dp[i-1][j-1])%MOD
print(dp[n][m])

### FIXED CODE ###

n, m = list(map(int, input().split()))
MOD = 10**9+7
dp = [[0 for i in range(2010)] for i in range(2010)]
for i in range(2010):
  dp[i][0] = 1
  dp[0][i] = 1
s = list(map(int, input().split()))
t = list(map(int, input().split()))
for i in range(1, n+1):
  for j in range(1, m+1):
    dp[i][j] = (dp[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1])%MOD
    if s[i-1]==t[j-1]:
      dp[i][j] = (dp[i][j]+dp[i-1][j-1])%MOD
print(dp[n][m])
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
keep = [0]*(n)

for i in range(1, n):
    l, r = i-1, i+1
    if s[l:r] == "AC":
        keep[i] = 1

for j in range(q):
    l, r = map(int, input().split())
    print(sum(keep[l:r]))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
keep = [0]*(n)

for i in range(1, n):
    keep[i] = keep[i-1]
    l, r = i-1, i+1
    if s[l:r] == "AC":
        keep[i] += 1

for j in range(q):
    l, r = map(int, input().split())
    print(keep[r-1]-keep[l-1])
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, H = MAP()
L = [LIST() for i in range(N)]

A = []
B = []
for a, b in L:
    A.append(a)
    B.append(b)

A.sort(reverse=True)
B.sort(reverse=True)

big_B = []

for b in B:
    if max(A) <= b:
        big_B.append(b)
thr = sum(big_B)
damage = 0 
cnt = 0

#
if thr >= H:
    # for i in range(N):
    # while damage < H:
    #     damage += B[i]
    #     cnt += 1
    i = 0
    cnt = len(big_B)
    while thr <= H:
        thr -= B[N-i-1]
        cnt -= 1

else:
    need_damage = H - thr
    cnt = len(big_B)
    if need_damage % A[0] == 0:
        cnt += need_damage // A[0]
    else:
        cnt += need_damage // A[0] + 1
print(cnt)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, H = MAP()
L = [LIST() for i in range(N)]

A = []
B = []
for a, b in L:
    A.append(a)
    B.append(b)

A.sort(reverse=True)
B.sort(reverse=True)

big_B = []

ma_A = max(A)
for b in B:
    if ma_A <= b:
        big_B.append(b)
thr = sum(big_B)
damage = 0 
cnt = 0
if thr >= H:
    for i in range(N):
        if damage < H:
            damage += B[i]
            cnt += 1
else:
    need_damage = H - thr
    cnt = len(big_B)
    if need_damage % A[0] == 0:
        cnt += need_damage // A[0]
    else:
        cnt += need_damage // A[0] + 1
print(cnt)
### BUGGY CODE ###

import bisect

N = int(input())
s = sorted(list(map(int,input().split())))
m = sorted(list(map(int,input().split())))
l = sorted(list(map(int,input().split())))
count = 0
for sitem in s:
  for mitem in m[bisect.bisect_right(m,sitem):]:
    count += len(l)-bisect.bisect_right(l,mitem)

print (count)


### FIXED CODE ###

import bisect

N = int(input())
s = sorted(list(map(int,input().split())))
m = sorted(list(map(int,input().split())))
l = sorted(list(map(int,input().split())))
count = 0
for mitem in m:
  count += bisect.bisect_left(s,mitem)*(N-bisect.bisect_right(l,mitem))
print (count)
### BUGGY CODE ###

n, k, q = input().split()
N = int(n)
K = int(k)
Q = int(q)
Q_list = []
for i in range(Q):
    Q_list.append(int(input()))

for i in range(N):
    p = K - (Q - Q_list.count(i + 1))
    if p <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

n, k, q = input().split()
N = int(n)
K = int(k)
Q = int(q)
Q_list = [0] * N
for i in range(Q):
    num = int(input())
    Q_list[num - 1] += 1

for i in range(N):
    p = K - (Q - Q_list[i])
    if p <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

N = int(input())
S = input()
dp = [[0] * 5005 for _ in range(5005)]
for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if S[i] != S[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i + 1][j + 1] + 1
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        now = min(dp[i][j], j - i)
        ans = max(ans, now)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
dp = [[0] * 5005 for _ in range(5005)]
for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if S[i] != S[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i + 1][j + 1] + 1
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        now = min(dp[i][j], j - i)
        ans = max(ans, now)
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
s=[int(input()) for i in range(m)]
l=[1]+[0]*(n)
INF=1000000007
if n ==1:
    print(1)
    exit()
if len(s)!=0 and s[0]== 1:l[1]=0
else:l[1]=1

for i in range(2,n+1):
    if i in s:num=0
    else:l[i] = (l[i-2]+l[i-1])%INF
print(l[-1])

### FIXED CODE ###

n,m = map(int,input().split())
s=set([int(input()) for i in range(m)])
l=[1]+[0]*n
INF=1000000007
if n ==1:
    print(1)
    exit()
if len(s)!=0 and 1 in s:l[1]=0
else:l[1]=1
for i in range(2,n+1):
    if i in s: l[i]=0
    else:l[i] = (l[i-2]+l[i-1])%INF
print(l[-1])
### BUGGY CODE ###

n=int(input())
for i in range(1,n+1):    
    c=0
    x=0
    y=0
    z=0
    for x in range(1,n):
        if x**2+y**2+z**2+x*y+y*z+z*x>i:
            break
        for y in range(1,n):
            if x**2+y**2+z**2+x*y+y*z+z*x>i:
                y=0
                break
            for z in range(1,n):
                if x**2+y**2+z**2+x*y+y*z+z*x>i:
                    z=0
                    break
                if x**2+y**2+z**2+x*y+y*z+z*x==i:
                    c+=1
    print(c)

### FIXED CODE ###

import math
n=int(input())
ansl=[0]*(n+1)  
c=0
x=0
y=0
z=0
rn=int(float(math.sqrt(n)))
for x in range(1,rn+1):
    for y in range(1,rn+1):
        for z in range(1,rn+1):
            if x**2+y**2+z**2+x*y+y*z+z*x<=n:
                ansl[x**2+y**2+z**2+x*y+y*z+z*x]+=1
for i in range(n):                
    print(ansl[i+1])
### BUGGY CODE ###

n = int(input())
c =0
for i in range(n):
    c+=i
print(c)

    


### FIXED CODE ###

a = int(input())
print((a*(a-1))//2)
### BUGGY CODE ###

import sys
from collections import Counter
from math import factorial

input = sys.stdin.readline

def conbi(n, r = 2):
    if n - r < 0:
        return 0
    return int(factorial(n) / (factorial(n - r) * factorial(r)))

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

for _ in A:
    ans = 0
    for cnt in A_cnt.keys():
        if A_cnt[cnt] == 1:
            continue
        else:
            if cnt == _:
                n = A_cnt[cnt] - 1
                ans += conbi(n)
            else:
                ans += conbi(A_cnt[cnt])
    print(ans)

### FIXED CODE ###

from collections import Counter

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

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

cnt = Counter(A)
ans = 0

for c in cnt.values():
    if c >= 2:
        ans += comb2(c)

for i in range(N):
    print(ans - cnt[A[i]] + 1)
### BUGGY CODE ###

N,Q = map(int,input().rstrip().split())
S = input().rstrip()
ans = 0
for _ in range(Q):
    l, r = map(int,input().rstrip().split())
    print(S[l-1:r].count('AC'))

### FIXED CODE ###

N,Q = map(int,input().rstrip().split())
S = input().rstrip()
a = [0]*N
for i in range(N):
    if i > 1:
        a[i] = a[i-1]
    if i != 0 and S[i-1]=='A' and S[i] == 'C':
        a[i] += 1
for _ in range(Q):
    l, r = map(int,input().rstrip().split())
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

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

a = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        a[i][j] = int(s[j])

best_result = h * w + 1000

for m in range(2 ** (h - 1)):
    mask = m
    num_splits = 0
    splits = []
    i = 0
    while mask > 0:
        if (mask % 2) == 1:
            num_splits += 1
            splits.append(i)
        i += 1
        mask = mask // 2

    #print('mask = ', m, 'splits = ', splits, 'num_splits =', num_splits)

    counts = [0 for j in range(num_splits + 1)]
    current_counts = [0 for j in range(num_splits + 1)]
    result = num_splits

    for j in range(w):
        if result >= best_result:
            break
        split_index = 0
        success = True
        current_counts[0] = 0

        for i in range(h):
            if a[i][j] == 1:
                counts[split_index] += 1
                if counts[split_index] > k:
                    success = False

            current_counts[split_index] += a[i][j]

            if split_index < num_splits and i == splits[split_index]:
                split_index += 1
                current_counts[split_index] = 0

        if not success:
            result += 1
            #print('not success j = ', j, 'result = ', result, 'counts = ', counts)
            for x in range(num_splits + 1):
                counts[x] = current_counts[x]
            

    best_result = min(best_result, result)

print(best_result)

### FIXED CODE ###

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

a = [[1 for i in range(w)] for j in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        a[i][j] = int(s[j])

best_result = h * w + 1000

for m in range(2 ** (h - 1)):
    mask = m
    num_splits = 0
    splits = []
    i = 0
    while mask > 0:
        if (mask % 2) == 1:
            num_splits += 1
            splits.append(i)
        i += 1
        mask = mask // 2

    #print('mask = ', m, 'splits = ', splits, 'num_splits =', num_splits)

    counts = [0 for j in range(num_splits + 1)]
    current_counts = [0 for j in range(num_splits + 1)]
    result = num_splits

    for j in range(w):
        if result >= best_result:
            break
        split_index = 0
        success = True
        current_counts[0] = 0

        for i in range(h):
            if a[i][j] == 1:
                counts[split_index] += 1
                if counts[split_index] > k:
                    success = False

            current_counts[split_index] += a[i][j]

            if split_index < num_splits and i == splits[split_index]:
                split_index += 1
                current_counts[split_index] = 0

        if not success:
            result += 1
            #print('not success j = ', j, 'result = ', result, 'counts = ', counts)
            fail = False
            for x in range(num_splits + 1):
                if current_counts[x] > k:
                    fail = True
                    break

                counts[x] = current_counts[x]
            if fail: 
                result = best_result + 1
                break
            

    best_result = min(best_result, result)

print(best_result)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(N-1):
    while A[i] > A[i+1]:
        A[i + 1] = A[i + 1] + 1
        count = count + 1
print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(1,N):
    if A[i-1] > A[i]:
        count += A[i-1] - A[i]
        A[i] = A[i - 1]
print(count)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    a.append(i+1+x[i])
    b.append(i+1-x[i])
ans = 0
for i in range(n):
    ans += b[i+1:].count(a[i])
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
x = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    a.append(i+1+x[i])
    b.append(i+1-x[i])
ans = 0
a, b = Counter(a), Counter(b)
for i in range(min(a), max(b)+1):
    ans += a[i]*b[i]
print(ans)