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

def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for i in range(N+1)] for j in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)

### FIXED CODE ###

def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m=map(int,input().split())
p=list(map(int,input().split()))
uf=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    uf.union(x-1,y-1)

ans=0
for List in list(uf.all_group_members().values()):
    tree=set()
    for i in range(len(List)):
        tree.add(p[List[i]])
    for g in range(len(List)):
        if List[g]+1 in tree:
            tree.remove(List[g]+1)
            ans+=1
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m=map(int,input().split())
p=list(map(int,input().split()))
uf=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    uf.union(x-1,y-1)

ans=0
for i in range(n):
    if uf.same(i,p[i]-1):
        ans+=1
print(ans)
### BUGGY CODE ###

import math
N, K = map(int, input().split())
S = list(map(int, input().split()))
d = [[0]*(N+1) for _ in range(math.ceil(math.log2(K)))]

for i in range(N):
    d[0][i+1] = S[i]

for i in range(1, math.ceil(math.log2(K))):
    for j in range(1, N+1):
        d[i][j] = d[i-1][d[i-1][j]]

ans = 1
for i in range(math.ceil(math.log2(K))):
    if (K >> i)&1:
        ans = d[i][ans]
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
S = list(num-1 for num in map(int, input().split()))
loc = 0

arrived = [0]*N
ar = set()
cnt = 0
while not loc in ar:
    arrived[cnt] = loc
    ar.add(loc)
    loc = S[loc]
    cnt += 1

if K < cnt:
    print(arrived[K]+1)
else:
    for i in range(cnt):
        if arrived[i] == loc:
            K -= i
            roop = cnt-i
            K %= roop
            print(arrived[i+K]+1)
            break
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1

S = [list(input().strip()) for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
used = [[False]*W for _ in range(H)]
q = deque([[cy, cx]])

worp = 0
while q:
    v = {}
    while q:
        y, x = q.popleft()
        used[y][x] = True
        worps[y][x] = min(worps[y][x], worp)

        for h in range(-2+y, 3+y):
            for w in range(-2+x, 3+x):
                if 0 <= h and h < H and 0 <= w and w < W and S[h][w] == ".":
                    v[(h, w)] = True

        for h, w in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            ny, nx = y+h, x+w
            if 0 <= ny and ny < H and 0 <= nx and nx < W:
                if not used[ny][nx] and S[ny][nx] == ".":
                    q.append([ny, nx])

    worp += 1
    for h, w in v.keys():
        if not used[h][w]:
            q.append([h, w])
            used[h][w] = True

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
S = [input() for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
q = deque([[cy, cx]])

worps[cy][cx] = 0
while q:
    y, x = q.popleft()
    worp = worps[y][x]

    for h, w in d:
        ny, nx = y+h, x+w
        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "." and worp < worps[ny][nx]:
            worps[ny][nx] = worp
            q.appendleft([ny, nx])

    worp += 1
    for h in range(-2+y, 3+y):
        for w in range(-2+x, 3+x):
            if 0 <= h < H and 0 <= w < W and S[h][w] == "." and worp < worps[h][w]:
                worps[h][w] = worp
                q.append([h, w])

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

# とても時間がかかる

def main():
    n = int(input())
    numlist = []
    for _ in range(n):
        numlist.append(int(input()))

    maxprofit = []
    for i in range(n-1):
        maxprofit.append(max(numlist[i+1:n]) - min(numlist[0:i+1]))
    print(max(maxprofit))


if __name__ == '__main__':
    main()



### FIXED CODE ###

n = int(input())
a0 = int(input())
a1 = int(input())
max_profit = a1 - a0
min_i = min(a1, a0)
for i in range(n-2):
    c=int(input())
    if c - min_i > max_profit:
        max_profit = c - min_i
    min_i = min(min_i, c)
print(max_profit)
### BUGGY CODE ###

a = input()
c = input()
d=[]
alist = list(a)
for i in range(int(c)):
  e = input().split()
  d.append(e)
for i in range(int(c)):
  if d[i][0]=="1":
    l = len(alist)
    for x in range(int(l//2)):
      alist[x],alist[l-x-1] = alist[l-x-1],alist[x]
  else:
    if d[i][1] == "1":
      alist = [d[i][2]] + alist
    else:
      alist = alist + [d[i][2]]
le = len(alist)
answer =""
answer = "".join(alist)
print(answer)

### FIXED CODE ###

from collections import deque
a = input()
c = input()
d = []
alist = list(a)
adeque = deque(a)
count = 0
for i in range(int(c)):
  e = input().split()
  d.append(e)
for i in range(int(c)):
  if d[i][0]=="1":
    count = count + 1
  else:
    if d[i][1] == "1" and count % 2 == 0:
      adeque.appendleft(d[i][2])
    elif d[i][1] == "2" and count % 2 == 1:
      adeque.appendleft(d[i][2])
    else:
      adeque.append(d[i][2])
alist = list(adeque)
if count % 2 == 1:
  l = len(alist)
  for x in range(int(l//2)):
    alist[x],alist[l-x-1] = alist[l-x-1],alist[x]
answer = "".join(alist)
print(answer)
### BUGGY CODE ###

BUFSIZE = 50
D = int(input())
C = list(map(int, input().split()))

c0 = sum(C)
Q = [(0, [], 0, [0]*26)]

for d in range(D):
    S = list(map(int, input().split()))
    Q2 = []
    
    for q in Q:
        sc, ts, c1, lasts = q
        c2 = c1 + c0

        for t in range(26):
            c3 = c2 - (d + 1 - lasts[t])*C[t]
            Q2.append((sc + S[t] - c3, ts, t, c3, lasts))

    Q = []
    sizeOfQ2 = len(Q2)
    for q in sorted(Q2, reverse=True)[:min(sizeOfQ2, BUFSIZE)]:
        sc, ts, t, c3, lasts = q
        lasts2 = lasts[:]
        lasts2[t] = d+1
        Q.append((sc, [ts, t], c3, lasts2))

# print(Q[0][0])
T = []
ts = Q[0][1]

for d in range(D):
    T.append(ts[1] + 1)
    ts = ts[0]

for t in reversed(T):
    print(t)



### FIXED CODE ###

BUFSIZE = 30
D = int(input())
C = list(map(int, input().split()))

c0 = sum(C)
Q = [(0, [], 0, [0]*26)]

for d in range(D):
    S = list(map(int, input().split()))
    Q2 = []
    
    for q in Q:
        sc, ts, c1, lasts = q
        c2 = c1 + c0

        for t in range(26):
            c3 = c2 - (d + 1 - lasts[t])*C[t]
            lasts2 = lasts[:]
            lasts2[t] = d+1
            Q2.append((sc + S[t] - c3, [ts, t], c3, lasts2))

    sizeOfQ2 = len(Q2)
    Q = sorted(Q2, reverse=True)[:min(sizeOfQ2, BUFSIZE)]

# print(Q[0][0])
T = []
ts = Q[0][1]

for d in range(D):
    T.append(ts[1] + 1)
    ts = ts[0]

for t in reversed(T):
    print(t)
### BUGGY CODE ###

k,s = map(int, input().split())
cnt = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l == s:
                cnt += 1
print(cnt)

### FIXED CODE ###

k,s = map(int, input().split())
cnt = 0
for i in range(k+1):
    for j in range(k+1):
            if 0 <= s-(i+j) <= k:
                cnt += 1
print(cnt)
### BUGGY CODE ###

import collections
import sys


readline = sys.stdin.buffer.readline


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    C = 10**9 + 7

    d = collections.defaultdict(int)

    for a in A:
        B = factorization(a)
        for b in B:
            d[b[0]] = max(d[b[0]], b[1])
    e = 1
    for k in d.keys():
        e *= k**d[k]

    ans = 0
    for a in A:
        ans += (e // a)
        ans %= C
    print(ans)


main()


### FIXED CODE ###

import collections
import sys

readline = sys.stdin.buffer.readline


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    C = 10**9 + 7

    d = collections.defaultdict(list)

    for a in A:
        B = factorization(a)
        for b in B:
            d[b[0]].append(b[1])
    e = 1
    for k, v in d.items():
        e *= k**max(v)

    ans = 0
    for a in A:
        ans += (e // a)
    print(ans % C)


main()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
    b = a.pop()
    ans *= b

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


### FIXED CODE ###

N = int(input())
ans = 1
A = [int(i) for i in input().split()]
ans = 1
for i in A:
    ans *= i
    if ans > 10**18:
        ans = -1
        break
if 0 in A:
    ans = 0
print(ans)
### BUGGY CODE ###

import heapq  # heapqライブラリのimoprt
N = int(input())
A = []

for i in range(N):
 a = int(input())
 A.append(-a)

A_init = A[:]
for i in range(N):
  A[i] = 0
  heapq.heapify(A)  # リストを優先度付きキューへ
  ans = -heapq.heappop(A) # 最小値の取り出し
  print(ans)
  A = A_init[:]

### FIXED CODE ###

import heapq  # heapqライブラリのimoprt
N = int(input())
A = []

for i in range(N):
 a = int(input())
 if(i == 0):
    A_max,A_max_index = a,i
 else: 
    if(A_max <= a):
      A_max,A_max_index = a,i
 A.append(a)

for i in range(N):
  if(i != A_max_index): 
    print(A_max)
  else:
    A[i] = 0
    A =  list(map(lambda x: x*(-1), A))
    heapq.heapify(A)
    ans = -heapq.heappop(A)
    print(ans)
### BUGGY CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

N = I()
L = LI()

L.sort()

ans = 0
for i, l in enumerate(L):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            if l + L[j] <= L[k]:
                break
            ans += 1

print(ans)

### FIXED CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N = I()
L = LI()

L.sort()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        c = bisect.bisect_left(L, L[i]+L[j])

        ans += max(0, c - (j+1))

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

n,q = (int(i) for i in input().split())
s = input()
a = {}
for i in range(n):
    if not s[i] in a:
        a[s[i]] = [i]
    else:
        a[s[i]].append(i)

nums = [1] * n
for i in range(q):
    td = list(input().split())
    t = td[0]
    d = td[1]
    if t in a:
        ids = a[t]
        for id in ids:
            if d == 'L':
                if id == 0:
                    nums[id] = 0
                else:
                    nums[id-1] += nums[id]    
                    nums[id] = 0
            else:
                if id == n-1:
                    nums[id] = 0
                else:
                    nums[id+1] += nums[id]
                    nums[id] = 0

print(sum(nums))

### FIXED CODE ###

n,q = (int(i) for i in input().split())
s = '#'+input()+'#'
l = 0
r = n+1
a = [list(input().split()) for i in range(q)]
for i in range(q-1, -1, -1):
    t,d = a[i]
    if s[l+1] == t and d =='L':
        l += 1
    elif s[l] == t and d == 'R':
        l -= 1
    if s[r] == t and d == 'L':
        r += 1
    elif s[r-1] == t and d == 'R':
        r -= 1
print(max(0,r-l-1))
### BUGGY CODE ###

N, M = map(int, input().split())
base = [[int(l) for l in input().split()] for i in range(M)]
sorted_target = sorted(base) 
  
prefecture_index = sorted_target[0][0]

i=0
result = {}

for target in sorted_target:
  if prefecture_index == target[0]:
    i+=1
  else:
    prefecture_index = target[0]
    i = 1
  result[base.index(target)] = [target[0], i]

for i in range(M):
  print("{:0=6}{:0=6}".format(result[i][0], result[i][1]))

### FIXED CODE ###

N, M = map(int, input().split())
base = []
for i in range(M):
  (a, b) = map(int, input().split())
  base.append((a, b, i))
sorted_target = sorted(base) 

prefecture_index = sorted_target[0][0]

i=0
result = {}

for target in sorted_target:
  if prefecture_index == target[0]:
    i+=1
  else:
    prefecture_index = target[0]
    i = 1
  result[target[2]] = [prefecture_index, i]

for i in range(M):
  print("{:0=6}{:0=6}".format(result[i][0], result[i][1]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h,w,m=map(int, input().split())
from collections import defaultdict
hd=defaultdict(int)
wd=defaultdict(int)
hd2=defaultdict(list)
wd2=defaultdict(list)
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hd2[h0].append(w0)
    wd[w0]+=1
    wd2[w0].append(h0)

max_h_list = [kv[0] for kv in hd.items() if kv[1] == max(hd.values())]
max_w_list = [kv[0] for kv in wd.items() if kv[1] == max(wd.values())]

ans=float('inf')

if len(max_h_list)>=len(max_w_list):
    for x in max_h_list:
        hlist=hd2[x]
        for y in max_w_list:
            if y in hlist:
                ans=min(ans,1)
            else:
                ans=min(ans,0)
else:
    for x in max_w_list:
        wlist=wd2[x]
        for y in max_h_list:
            if y in wlist:
                ans=min(ans,1)
            else:
                ans=min(ans,0)
print(hd[max_h_list[0]]+wd[max_w_list[0]]-ans)


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
h,w,m=map(int, input().split())
hd=[0 for i in range(h+1)]
wd=[0 for i in range(w+1)]
hw=defaultdict(int)
hmax=0
wmax=0
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hmax=max(hmax,hd[h0])
    wd[w0]+=1
    wmax=max(wmax,wd[w0])
    hw[(h0,w0)]+=1

max_h_list=[]
max_w_list=[]
for k in range(h+1):
    if hd[k]==hmax:
        max_h_list.append(k)

for k in range(w+1):
    if wd[k]==wmax:
        max_w_list.append(k)

ans=float('inf')

for x in max_h_list:
    for y in max_w_list:
        if hw[(x,y)]==1:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
            break
print(hmax+wmax-ans)
### BUGGY CODE ###

import heapq,sys


def main():
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    A = sorted([int(i) for i in input().split()], reverse=True)
    B = sorted([int(i) for i in input().split()], reverse=True)
    C = sorted([int(i) for i in input().split()], reverse=True)
    ans = []
    heap_queue = []
    for i in range(X):
        for j in range(Y):
            for k in range(Z):
                heapq.heappush(heap_queue, A[i] + B[j] + C[k])
                #要素がK個以上ならはじく！！！ことでO(logK)
                if len(heap_queue) > K:
                    heapq.heappop(heap_queue)
    heap_queue.sort(reverse = True)
    for e in heap_queue:
        print(e)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,bisect
input = sys.stdin.readline

x,y,z,k = map(int,input().split())
a = tuple(map(int,input().split()))
b = tuple(map(int,input().split()))
c = list(map(int,input().split()))

ab = []
for e in a:
    for w in b:
        ab.append(e+w)
ab.sort()

ok = -1
ng = 10**12
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    cnt = 0
    for e in c:
        cnt += len(ab)-bisect.bisect_left(ab,mid-e)
    if cnt >= k:
        ok = mid
    else:
        ng = mid

res = []
for e in c:
    ind = bisect.bisect_left(ab,ok-e)
    for i in range(ind,len(ab)):
        res.append(e+ab[i])
res.sort()
for i in range(1,k+1):
    print(res[-i])
### BUGGY CODE ###

from fractions import gcd

def main():
    input()
    aa = list(map(int, raw_input().split()))
    g = 1
    for a in aa:
        g = a * g // gcd(a, g)
    ans = 0
    for a in aa:
        ans = (ans + g // a) % (10 ** 9 + 7)
    print(ans)


main()


### FIXED CODE ###

from fractions import gcd

def main():
    n = input()
    aa = list(map(int, raw_input().split()))
    g = 1
    for a in aa:
        g *= a // gcd(a, g)
    ans = 0
    MOD = 10 ** 9 + 7
    g %= MOD
    for a in aa:
        ans = (ans + g * pow(a, MOD - 2, MOD)) % MOD
    print(ans)


main()
### BUGGY CODE ###

import numpy as np

n = int(input())
h = list(map(int, input().split()))
ans = 0
for i in range(n-1):
    if h[i] > n - i - 1:
        continue
    num = min(n, i + h[i] + 1)
    s = np.array(h[num:])
    length = len(s)
    u = np.arange(length) + 1
    s -= u
    t = np.count_nonzero(s)
    ans += length - t
print(ans)


### FIXED CODE ###

from collections import Counter

n = int(input())
h = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    a.append(i + h[i])
    b.append(i - h[i])

x = Counter(a)
y = Counter(b)

z = set(a)
ans = 0
for i in z:
    ans += x[i] * y[i]

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

x,k,d = map(int, input().split())
def  abs_calc(x):
    if  x <  0:
        xi =  (-1)* x
    else:
        xi  = x
    return xi
xi = abs_calc(x)
ans = xi + k * d
for i in range(k+1):
    xx  = x +  d*i + (-1)*d*(k-i)
    xxi = abs_calc(xx)
    if xxi < ans:
        ans = xxi
print(ans)


### FIXED CODE ###

x,k,d = map(int, input().split())
def  abs_calc(x):
    if  x <  0:
        xi =  (-1)* x
    else:
        xi  = x
    return xi


xi = abs_calc(x)
a = xi // d
if a >= k:
    ans = xi - d * k
else:
    k  -= a
    ans = xi - d * a
    if  k %  2 != 0:
        ans =  d - ans
print(ans)
### BUGGY CODE ###

import math

n = int(input())
s = input()
s2 = list(s)

if s[0] == 'B':
    s2[0] = 'L'
else:
    s2[0] = 'R'

for i in range(1,2*n): 
    if s[i-1] == s[i]:
        if s2[i-1] == 'L':
            s2[i] = 'R'
        else:
            s2[i] = 'L'
    else:
        if s2[i-1] == 'L':
            s2[i] = 'L'
        else:
            s2[i] = 'R'

count_l = 0
count_r = 0
for i in range(2*n): 
    if s2[i] == 'L':
        count_l += 1
    else:
        count_r += 1
        
if s2[0] == 'R' or s2[2*n-1] == 'L' or count_l != count_r:
    print(0)
    exit()
            
ans = 1
count_l = 0
for i in range(0,2*n): 
    if s2[i] == 'L':
        count_l += 1
    else:
        ans *= count_l
        count_l -= 1
    
print((ans * math.factorial(n)) % (10**9 + 7))

### FIXED CODE ###

import math

n = int(input())
s = input()
s2 = list(s)

if s[0] == 'B':
    s2[0] = 'L'
else:
    s2[0] = 'R'

for i in range(1,2*n): 
    if s[i-1] == s[i]:
        if s2[i-1] == 'L':
            s2[i] = 'R'
        else:
            s2[i] = 'L'
    else:
        if s2[i-1] == 'L':
            s2[i] = 'L'
        else:
            s2[i] = 'R'
        
if s2[0] == 'R' or s2[2*n-1] == 'L' or s2.count('L') != s2.count('R'):
    print(0)
    exit()
            
ans = 1
count_l = 0
for s2_str in s2: 
    if s2_str == 'L':
        count_l += 1
    else:
        ans *= count_l
        ans %= 10**9 + 7
        count_l -= 1
    
print(ans * math.factorial(n) % (10**9 + 7))