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

import numpy as np
N=int(input())
s=input()
count=[]
west=[]
east=[]
for i in range(N):
    west.append(0)
    east.append(0)
    if(s[i]=='W'):
        west[i]=1
    else:
        east[i]=1
eastsum=np.zeros(N)
westsum=np.zeros(N)
for i in range(N):
    eastsum[i]=sum(east[i:])-east[i]
    westsum[i]=sum(west[:i])
print(int(np.min(eastsum+westsum)))

### FIXED CODE ###

import numpy as np
N=int(input())
s=input()
west=[]
east=[]
for i in range(N):
    west.append(0)
    east.append(0)
    if(s[i]=='W'):
        west[i]=1
    else:
        east[i]=1
eastsum=np.zeros(N)
westsum=np.zeros(N)
westsum[0]=west[0]
eastsum[N-1]=east[N-1]
for i in range(1,N):
    eastsum[N-1-i]=eastsum[N-i]+east[N-1-i]
    westsum[i]=westsum[i-1]+west[i]
print(int(np.min(eastsum+westsum))-1)
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import Counter
import bisect
from decimal import *
def main():
    N, D, A = MI()
    Enemy = []
    for i in range(N):
        x, h = MI()
        Enemy.append([x, h])
    Enemy.sort(key=lambda list: list[0])
    Enemy_Ran = []
    for ene in Enemy:
        Enemy_Ran.append(ene[0])


    cnt = 0
    for i in range(N):
        if Enemy[i][1] <= 0:
            continue
        else:
            ata = math.ceil(Decimal(Enemy[i][1]) / Decimal(A))
            cnt += ata
            ran = Enemy[i][0] + 2 * D
            ran_i = bisect.bisect_right(Enemy_Ran, ran)
            dam = ata * A
            for j in range(i + 1, ran_i):
                Enemy[j][1] -= dam

    print(cnt)


if __name__ == "__main__":
    main()



### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import defaultdict
from collections import deque
import bisect
from decimal import *
def main():
    N, D, A = MI()
    Enemy = defaultdict()
    Enemy_ran = []
    for i in range(N):
        x, h = MI()
        Enemy[x] = h
        Enemy_ran.append(x)
    Enemy_ran.sort()
    cnt = 0
    dam_list = deque()
    dam_all = 0
    for i in range(N):
        x = Enemy_ran[i]
        while len(dam_list) != 0 and i >= dam_list[0][0]:
            dam_all -= dam_list.popleft()[1]
        HP = Enemy[x] - dam_all
        if HP <= 0:
            continue
        else:
            ata = math.ceil(Decimal(HP) / Decimal(A))
            cnt += ata
            ran = x + 2 * D
            y = bisect.bisect_right(Enemy_ran, ran)
            dam = ata * A
            dam_list.append((y, dam))
            dam_all += dam


    print(cnt)


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

import bisect

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

Goal=[[] for _ in range(N)]
for i in range(M):
    L,R=map(int,input().split())
    Goal[L-1].append(R-1)

for i in range(1,N)[::-1]:
    Goal[i-1]+=Goal[i]

for i in range(N):
    Goal[i].sort()

ans=[]
for g in range(Q):
    p,q=map(int,input().split())
    ans.append(bisect.bisect_right(Goal[p-1],q-1))

for l in range(Q):
    print(ans[l])

### FIXED CODE ###

from collections import defaultdict

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

Goal=[defaultdict(int) for _ in range(N)]
for i in range(M):
    L,R=map(int,input().split())
    Goal[L-1][R-1]+=1

Accumlate = [[0]*(N+1) for i in range(N)]
for g in range(N):
    for l in range(N):
        Accumlate[g][l+1]+=Accumlate[g][l]+Goal[g][l]

ans_list=[]
for l in range(Q):
    ans=0
    L,R=map(int,input().split())
    for l in range(L-1,R):
        ans+=Accumlate[l][R]-Accumlate[l][L-1]
    ans_list.append(ans)

for m in range(Q):
    print(ans_list[m])
### BUGGY CODE ###

def main():
    N, M, K = map(int, input().split())

    fac = [0] * N
    fac[0] = 1
    for i in range(N - 1):
        fac[i + 1] = fac[i] * (i + 1) % 998244353

    def mcomb(n, k, fac):
        if n == 0 and k == 0:
            return 1
        if n < k or k < 0:
            return 0
        return fac[n] * pow(fac[n - k], 998244351, 998244353) * pow(fac[k], 998244351, 998244353) % 998244353

    result = 0
    for i in range(K + 1):
        result += M * mcomb(N - 1, i, fac) * pow(M - 1, N - 1 - i, 998244353)
        result %= 998244353
    print(result)


main()


### FIXED CODE ###

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

result = 0
n = 1
k = 1
for i in range(K + 1):
    result += n * pow(k, 998244353 - 2, 998244353) * pow(M - 1, N - 1 - i, 998244353)
    result %= 998244353
    n *= N - 1 - i
    n %= 998244353
    k *= i + 1
    k %= 998244353
result *= M
result %= 998244353
print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def solve():
    INF = float('inf')

    def max2(x, y): return x if x >= y else y

    R, C, K = map(int, input().split())
    Vss = [[0]*(C+1) for _ in range(R+1)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        Vss[r][c] = v

    dp = [[[-INF]*(4) for j in range(C+1)] for i in range(R+1)]
    for i in range(R+1):
        dp[i][0][0] = 0
    for j in range(C+1):
        dp[0][j][0] = 0
    dpMax = [[0]*(C+1) for _ in range(R+1)]

    for i in range(1, R+1):
        for j in range(1, C+1):
            V = Vss[i][j]
            dp[i][j][0] = max2(dp[i][j-1][0], dpMax[i-1][j])
            dp[i][j][1] = max2(dp[i][j][0] + V, dp[i][j-1][1])
            dp[i][j][2] = max2(dp[i][j-1][1] + V, dp[i][j-1][2])
            dp[i][j][3] = max2(dp[i][j-1][2] + V, dp[i][j-1][3])
            dpMax[i][j] = max(dp[i][j])

    ans = dpMax[R][C]
    print(ans)


solve()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def solve():
    INF = float('inf')

    def max2(x, y): return x if x >= y else y

    R, C, K = map(int, input().split())
    Vss = [[0]*(C+1) for _ in range(R+1)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        Vss[r][c] = v

    dpMax = [0]*(C+1)
    for i in range(1, R+1):
        dp0 = [0]*(C+1)
        dp1 = [-INF]*(C+1)
        dp2 = [-INF]*(C+1)
        dp3 = [-INF]*(C+1)
        for j in range(1, C+1):
            V = Vss[i][j]
            dp0[j] = max2(dp0[j-1], dpMax[j])
            dp1[j] = max2(dp0[j] + V, dp1[j-1])
            dp2[j] = max2(dp1[j-1] + V, dp2[j-1])
            dp3[j] = max2(dp2[j-1] + V, dp3[j-1])
            dpMax[j] = max(dp0[j], dp1[j], dp2[j], dp3[j])

    ans = dpMax[C]
    print(ans)


solve()
### BUGGY CODE ###

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
ss = set(r)
r.sort()
d = [[float("inf")] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
  a, b, c = map(int, input().split())
  d[a][b] = c
  d[b][a] = c
res = float("inf")
for s in range(1, N + 1):
  dp = [[float("inf")] * (pow(2, R)) for _ in range(N + 1)]
  if s in r:
    dp[s][1 << bl(r, s)] = 0
  else: continue
  for i in range(1, N + 1):
    for j in range(pow(2, R)):
      for k in range(1, N + 1):
        x = bl(r, k)
        if j & (1 << x):
          continue
        #print(j, k, j + (1 << x))
        if k in ss:
          dp[k][j + (1 << x)] = min(dp[k][j + (1 << x)], dp[i][j] + d[i][k])
        else: dp[k][j] = min(dp[k][j], dp[i][j] + d[i][k])
  for i in range(1, N + 1):
    res = min(res, dp[i][-1])
print(res)

### FIXED CODE ###

import sys
from itertools import permutations as per
input = sys.stdin.readline
N, M, R = map(int, input().split())
r = list(map(int, input().split()))
d = [[float("inf")] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
  d[i][i] = 0
for _ in range(M):
  a, b, c = map(int, input().split())
  d[a][b] = c
  d[b][a] = c

for k in range(1, N + 1):
  for i in range(1, N + 1):
    for j in range(1, N + 1):
      d[i][j] = min(d[i][k] + d[k][j], d[i][j])
res = float("inf")
for p in per(r, R):
  t = 0
  for i in range(R - 1):
    t += d[p[i]][p[i + 1]]
  res = min(t, res)
print(res)
### BUGGY CODE ###

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

count = 0

for i in range(0, len(lstP)):
    lstT = lstP[0:i+1]
    if min(lstT) == lstP[i]:
        count = count + 1

print(count)

### FIXED CODE ###

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

count = 1
minval = lstP[0]

for i in range(1, len(lstP)):
    val = lstP[i]
    if val <= minval:
        minval = val
        count += 1

print(count)
### BUGGY CODE ###

# K回前と現在の問いが同じだったら0点

str1 = input().split(" ")
str2 = input().split(" ")
t = input()

n = int(str1[0])
k = int(str1[1])

r = int(str2[0])
s = int(str2[1])
p = int(str2[2])

skill = {"r":p,"s":r,"p":s}

result = 0
douchilist = []
for i in range(0,n):
    if i >= k:
        if t[i] == t[i-k] and i-k not in douchilist:
            result += 0
            douchilist.append(i)
            continue

    result += skill[t[i]]
    continue


print(result)

### FIXED CODE ###

# K回前と現在の問いが同じだったら0点

str1 = input().split(" ")
str2 = input().split(" ")
t = list(input())

n = int(str1[0])
k = int(str1[1])

r = int(str2[0])
s = int(str2[1])
p = int(str2[2])

result = 0
hoge = 0
for i in range(0,n):
    if i < k:
        continue

    j = i-k
    if t[i] == t[j]:
        t[i] = "_"

pres = p * t.count("r")
rres = r * t.count("s")
sres = s * t.count("p")

print(pres + rres + sres)
### BUGGY CODE ###

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

mod = 10**9+7
 
def modcmb(n, r, mod):
    x = 1
    y = n
    for i in range(2,r+1):
        x *= i
        x %= mod
        y *= n-i+1
        y %= mod
    
    return y * pow(x, mod-2, mod) % mod

def resolve():
    ans = (pow(2, n) - modcmb(n, a, mod) - modcmb(n, b, mod) - 1) % mod
    print(ans)

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

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

MOD = 10**9+7

def modcmb(n, r, m):
    x = 1
    y = n
    for i in range(2,r+1):
        x *= i
        x %= MOD
        y *= n-i+1
        y %= MOD
    return y * pow(x, m-2, m) % m

ans = pow(2, N, MOD) - modcmb(N, a, MOD) - modcmb(N, b, MOD) - 1
print(ans % MOD)
### BUGGY CODE ###

def isPrime(num):
    if num < 2:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    for i in range(3, int(num**0.5)+1, 2):
        if num % i == 0:
            return False
    return True

def is_2017(num):
    temp = (num + 1) // 2
    if isPrime(num) and isPrime(temp):
        return True
    else:
        return False

if __name__ == "__main__":
        
    Q = int(input())
    l_r = [tuple(map(int, input().split())) for _ in range(Q)]
    answer_list = []
    for l, r in l_r:
        count = 0
        for i in range(l, r+1, 2):
            count += is_2017(i)
        answer_list.append(count)

    for ans in answer_list:
        print(ans)




### FIXED CODE ###

def isPrime(num):
    if num < 2:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False

    for i in range(3, int(num**0.5)+1, 2):
        if num % i == 0:
            return False
    return True

def is_2017(num):
    temp = (num + 1) // 2
    if isPrime(num) and isPrime(temp):
        return True
    else:
        return False

if __name__ == "__main__":
    
    is_2017_list = [0] * (10**5 + 1)
    count = 0
    for i in range(1, 10**5):
        if is_2017(i):
            count += 1
            is_2017_list[i] = count
            
        else:
            is_2017_list[i] = count

    Q = int(input())

    ans_list = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans = is_2017_list[r] - is_2017_list[l-1]
        ans_list.append(ans)
    
    for ans in ans_list:
        print(ans)
### BUGGY CODE ###

import collections
N=int(input())
S=[input() for i in range(N)]

C=collections.Counter(S)
max_C_list=sorted([i[0] for i in C.items() if i[1]==max(C.values())])

for i in max_C_list:
    print(i)

### FIXED CODE ###

import collections
N=int(input())
S=[input() for i in range(N)]

C=collections.Counter(S)
C_S=C.most_common()
m=C.most_common()[0][1]
ans=[]

for i in range(len(C_S)):
    if C_S[i][1]!=m:
        break
    else:
        ans.append(C_S[i][0])

ans.sort()

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

def nCr(n,r):
  dividend = 1
  divisor = 1
  MOD = 10**9+7
  d1 = n
  for i in range(1,r+1):
    dividend *= d1
    divisor *= i
    d1 -= 1
    dividend %= MOD
    divisor %= MOD

  return (dividend * pow(divisor, MOD-2, MOD)) % MOD


N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
MOD = 10**9+7

ans = 0
for i in range(N-K+1):
  ans -= A[i] * nCr(N - i - 1, K - 1) % MOD
  ans %= MOD

A = A[::-1]
for i in range(N-K+1):
  ans += A[i] * nCr(N - i - 1, K - 1) % MOD
  ans %= MOD

print(ans % MOD)


### FIXED CODE ###

class Combination:
  def __init__(self, n_max, mod=10**9+7):
    self.mod = mod
    self.modinv = self.make_modinv_list(n_max)
    self.fac, self.facinv = self.make_factorial_list(n_max)

  def __call__(self, n, r):
    return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

  def make_factorial_list(self, n):
    # 階乗のリストと階乗のmod逆元のリストを返す O(n)
    # self.make_modinv_list()が先に実行されている必要がある
    fac = [1]
    facinv = [1]
    for i in range(1, n+1):
      fac.append(fac[i-1] * i % self.mod)
      facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
    return fac, facinv

  def make_modinv_list(self, n):
    # 0からnまでのmod逆元のリストを返す O(n)
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
      modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
    return modinv

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
MOD = 10**9+7

comb = Combination(10**5+1)

ans = 0
for i in range(N-K+1):
  ans -= A[i] * comb(N - i - 1, K - 1) % MOD
  ans %= MOD

A = A[::-1]
for i in range(N-K+1):
  ans += A[i] * comb(N - i - 1, K - 1) % MOD
  ans %= MOD

print(ans % MOD)
### BUGGY CODE ###

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

i=0
count=0

while count+i<N:
    if a[i]==i+1:
        i+=1
    else:
        count+=1
        a.pop(i)
if count<N:
    print(count)
else:
    print(-1)

### FIXED CODE ###

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

base=1
count=0

if 1 in a:
    for i in range(N):
        if a[i]==base:
            count+=1
            base+=1
        else:
            pass

    #print(i)
    print((N-count)%N)
else:
    print(-1)
### BUGGY CODE ###

import sys
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
bc = []
for q in range(Q):
    b, c = map(int, input().split())
    A = [c if b == a else a for a in A]
    print(sum(A))

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
cnt = collections.Counter(A)
Q = int(input())
ans = []
s = sum(A)
for _ in range(Q):
    b, c = map(int, input().split())
    n = cnt[b]
    if b in cnt:
        cnt[c] += cnt[b]
        del cnt[b]
    s += (c-b)*n
    print(s)
### BUGGY CODE ###

N, A, B = input().rstrip().split(' ')
N = int(N)
A = int(A)
B = int(B)
n = int(N / (A+B)) * A
m = N % (A+B)

b = ''
r = ''
br = ''
for _ in range(A):
    b += 'b'
for _ in range(B):
    r += 'r'
br = b+r
print(n + br[:m].count('b'))

### FIXED CODE ###

N, A, B = input().rstrip().split(' ')
N = int(N)
A = int(A)
B = int(B)

n = int(N / (A+B)) * A
m = N % (A+B)

if m > A:
    m = A
print(n + m)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
result = {}
count = []
count = [0 for i in range(N)]

for i in range(1, len(A)+2):
    for j in A:
        if(j == i):
            count[i-1] = count[i-1]+1
            
for i in range(i):
    print(count[i])


### FIXED CODE ###

import collections
N = int(input())
strA = input().split()
ans = collections.Counter(strA)
for i in range(1, N+1):
    print(ans[str(i)])
### BUGGY CODE ###

#C
#モジュール
import numpy as np
#入力
N,K,Q=map(int,input().split())
A=[int(input()) for i in range(Q)]
pt=np.array([K for i in range(N)])

#処理
#点数の算出
for i in A:
    pt[:i-1]=pt[:i-1]-1
    pt[i:]=pt[i:]-1
#敗退か否かの出力
for i in pt:
    if i>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

#C
#入力
N,K,Q=map(int,input().split())
A=[int(input())-1 for i in range(Q)]

#処理
B=[0 for i in range(N)]

for i in A:
    B[i]+=1

for i in B:
    if Q-i<K:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

max = 0

for i in range(N-K+1):
    tmp = p[i]
    # print("i:" + str(i))
    for j in range(i+1,i+K):
        tmp += p[j]

    # print(tmp)
    if(max < tmp):
        max = tmp 
        maxStartIndex = i
ans = 0
for i in range(maxStartIndex, maxStartIndex+K):
    sum = p[i] * (p[i]+1) / 2
    ans += sum/p[i]
print('{:.12f}'.format(ans))
# 1 2 3 
# 3 2 1


# n, n-1, n-2
# n(n + 1)/2 

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
p_sum = [0]
max = 0

for i in range(len(p)):
    p_sum.append(p_sum[i] + (p[i]+1)/2) 

for i in range(K,N+1):
    sum = p_sum[i] - p_sum[i-K]
    if(max < sum):
        max = sum
# for i in range(N-K+1):
#     tmp = p[i]
#     # print("i:" + str(i))
#     for j in range(i+1,i+K):
#         tmp += p[j]

#     # print(tmp)
#     if(max < tmp):
#         max = tmp 
#         maxStartIndex = i
# ans = 0
# for i in range(maxStartIndex, maxStartIndex+K):
#     sum = p[i] * (p[i]+1) / 2
#     ans += sum/p[i]
print('{:.12f}'.format(max))
# 1 2 3 
# 3 2 1


# n, n-1, n-2
# n(n + 1)/2
### BUGGY CODE ###

A, B, C, K =map(int, input().split())

ans = 0
for i in range(K):
    if A != 0:
        ans+=1
        A-=1

    else:
        if B != 0:
            ans+=0
            B-=1
        else:
            if C != 0:
                ans-=1
                C-=1

print(ans)  

### FIXED CODE ###

A, B, C, K =map(int, input().split())

ans = 0

if A <= K:
    ans = ans + A
    K = K-A
    if B <= K:
        K = K-B
        if C >= K:
            ans = ans - K
            print(ans)
    else:
        print(ans)
else:
    print(K)
### BUGGY CODE ###

num,renzoku=map(int,input().split())
dices=list(map(int,input().split()))
expects=[0]*num
for i in range(num):
  pi=dices[i]
  expects[i]=(1+pi)/2
expects_list=[]
for i in range(0,num-renzoku+1):
  expects_list.append(sum(expects[i:i+renzoku]))
print(max(expects_list))

### FIXED CODE ###

num,renzoku=map(int,input().split())
dices=list(map(int,input().split()))
expects=[0]*num
for i in range(num):
  pi=dices[i]
  expects[i]=(1+pi)/2
Si=[0]*(num+1)
for i in range(1,num+1):
  Si[i]=Si[i-1]+expects[i-1]
max_Si=0
for i in range(0,num-renzoku+1):
  if max_Si<Si[i+renzoku]-Si[i]:
    max_Si=Si[i+renzoku]-Si[i]
print(max_Si)
### BUGGY CODE ###

n,k=map(int,input().split())
A=sorted(map(int,input().split()))
C=[1]
for i in range(n-k):
    c=C[i]*(k+i)//(i+1)
    C.append(c)
ans=0
for i in range(n-k+1):
    ans+=C[-i-1]*(A[-i-1]-A[i])
ans%=1000000007
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
A=sorted(map(int,input().split()))

def cmb(n,r,mod):
    if (r<0 or r>n):
        return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod

mod=10**9+7
N=10**5
g1=[1,1]
g2=[1,1]
inverse=[0,1]

for i in range(2,N+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)

ans=0
for i in range(n-k+1):
    ans+=cmb(n-1-i,k-1,10**9+7)*(A[-i-1]-A[i])%(10**9+7)
    ans%=10**9+7
print(ans)
### BUGGY CODE ###

import math

K=int(input())
ans=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans+=math.gcd(math.gcd(i,j),k)
print(ans)


### FIXED CODE ###

import math

N=int(input())
ans=0
for i in range(1,N+1):
    for j in range(i,N+1):
        for k in range(j,N+1):
            if i==j and j==k:
                ans+=i
            elif i<j and j<k:
                ans+=6*math.gcd(i,math.gcd(j,k))
            else:
                ans+=3*math.gcd(i,math.gcd(j,k))
print(ans)
### BUGGY CODE ###

N=int(input())
listA=list(map(int,input().split()))
ans=0
for i in range(N-1):
  if listA[i]<N-i:
    for k in range(i+1,N):
      if k-i==listA[i]+listA[k]:
        ans+=1
print(ans)        

### FIXED CODE ###

N=int(input())
listA=list(map(int,input().split()))
ans=0
L=[]
R=[]
L1=[0]*N
R1=[0]*N
for i in range(N):
  L+=[i+listA[i]]
  R+=[i-listA[i]]
  try:
    L1[i+1+listA[i]]+=1
  except:
    pass
  try:
    if i-listA[i]>0:
      R1[i+1-listA[i]]+=1
  except:
    pass
for i in range(N):
  ans+=L1[i]*R1[i]
print(ans)
### BUGGY CODE ###

def main():

    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse = True)

    ans = P
    for i in range(P, N):
        v = P * M + (N-1-i-1+1) * M
        for j in range(P-1, i):
            v += min(A[i] + M - A[j], M)
        if v >= M * V:
            ans += 1
    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import bisect
def main():

    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    prefix = [0]
    for i in range(N):
        prefix.append(prefix[-1] + A[i])

    ans = P
    for i in range(N-P):
        if A[i] + M >= A[N-P]:
            v = i * M + P * M
            v += (A[i] + M) * (N-P-i)
            v -= prefix[N-P+1] - prefix[i+1]
            if v >= M * V:
                ans += 1

    return ans

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

n,a,b = map(int,input().split())
mod = 10**9 + 7
ans = pow(2,n,mod) - 1
fact = [1]
finv = [1]
for i in range(1, n+1):
    fact += [(fact[i-1] * i) % mod]
    finv += [pow(fact[i], mod-2, mod)]
print((ans - (fact[n]*finv[n-a]*finv[a]) % mod - (fact[n]*finv[n-b]*finv[b]) % mod) % mod)

### FIXED CODE ###

n,a,b = map(int,input().split())
mod = 10**9 + 7
ans = pow(2,n,mod) - 1
fa = 1
fb = 1
for i in range(1, a+1):
    fa *= i
    fa %= mod
for i in range(1, b+1):
    fb *= i
    fb %= mod

fa = pow(fa, mod-2, mod)
fb = pow(fb, mod-2, mod)

for i in range(a):
    fa *= n - i
    fa %= mod
for i in range(b):
    fb *= n - i
    fb %= mod

print((ans - fa - fb) % mod)
### BUGGY CODE ###

from collections import deque
n=int(input())
a=deque(map(int,input().split()))
b=[]
for i in range(n):
    b.append(a.popleft())
    b=b[::-1]
print(*b)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
b=[0]*n
cnt=0
for i in range(n):
    if i%2==0:
        b[cnt]=A.pop()
        cnt+=1
    else:
        b[-cnt]=A.pop()

print(*b)
### BUGGY CODE ###

import queue

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

fri=[[] for i in range(n)]

for i in range(m):
  ai,bi=map(int,input().split())
  fri[ai-1].append(bi-1)
  fri[bi-1].append(ai-1)

seen=[0 for i in range(n)]



ans=0
for i in range(n):
  if seen[i]==1:
    continue
  cnt=1
  q=queue.Queue()
  q.put(i)
  seen[i]=1
  while not q.empty():
    p=q.get()
    for pnext in fri[p]:
      if seen[pnext]==0:
        q.put(pnext)
        seen[pnext]=1
        cnt+=1
  ans=max(ans,cnt)

print(ans)

### FIXED CODE ###

import queue

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

fri=[[] for i in range(n)]

for i in range(m):
  ai,bi=map(int,input().split())
  fri[ai-1].append(bi-1)
  fri[bi-1].append(ai-1)

seen=[0 for i in range(n)]



ans=0
for i in range(n):
  if seen[i]==1:
    continue
  cnt=1
  q=queue.Queue()
  q.put(i)
  seen[i]=1
  while not q.empty():
    p=q.get()
    for pnext in fri[p]:
      if seen[pnext]==0:
        q.put(pnext)
        seen[pnext]=1
        cnt+=1
  ans=max(ans,cnt)

print(ans)