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

def E(x):
    return (x+1)/2

N,K = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

print(max([sum([E(p[-i]) for i in range(j,K+j)]) for j in range(N-K+1)]))

### FIXED CODE ###

N,K = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

s = sum([p[i] for i in range(K)])
data = [s]
for i in range(N-K):
    s = s-p[i]+p[i+K]
    data.append(s)
print((max(data)+K)/2)
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

a, b, N = MAP()

ans = -INF
for x in range(N+1):
    ans = max(ans, a*x // b - a*(x//b))
print(ans)


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

a, b, N = MAP()

# for x in range(N+1):
#     print(a*x // b - a*(x//b))

x = min(b-1, N)
ans = a*x // b - a*(x//b)
print(ans)
### BUGGY CODE ###

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

H,W = map(int,input().split())

maze = []
for _ in range(H):
    maze.append(input())
    
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0
len_q = len(q)

#print(start)
def bfs(h,w,q,Saitan,len_Q):
    
    while q and len_Q < h * w:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for i,k in ([1,0],[-1,0],[0,1],[0,-1]):
            my = y + i
            mx = x + k
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            len_Q += 1
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan,len_q))
#print(saitan)

### FIXED CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0
len_q = len(q)

#print(start)
def bfs(h,w,q,Saitan,len_Q):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and len_Q < h * w:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            len_Q += 1
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan,len_q))
#print(saitan)
### BUGGY CODE ###

n, p = map(int, input().split())
s = input()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    s2 = s[::-1]
    rems = [0]
    tmp = 0
    for i in range(n):
        tmp += int(s2[i]) * 10 ** i
        tmp %= p
        rems.append(tmp)

    from collections import Counter
    counter = Counter(rems)
    ans = 0
    for key in counter.keys():
        v = counter[key]
        ans += v * (v - 1) // 2
print(ans)


### FIXED CODE ###

n, p = map(int, input().split())
s = input()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    s2 = s[::-1]
    rems = [0]
    tmp = 0
    tmp2 = 1
    for i in range(n):
        tmp += int(s2[i]) * tmp2
        tmp %= p
        tmp2 *= 10
        tmp2 %= p
        rems.append(tmp)

    from collections import Counter
    counter = Counter(rems)
    ans = 0
    for key in counter.keys():
        v = counter[key]
        ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

from collections import defaultdict
q = int(input())
for _ in range(q):
    x = input()
    y = input()
    len_x = len(x)
    len_y = len(y)
    if len_x < len_y:
        len_x, len_y = len_y, len_x
        x, y = y, x
    set_x = set(x)
    c = defaultdict(list)
    for i, s in enumerate(x):
        c[s].append(i)
    li = [0] * len_x
    for s in y:
        for i in c[s][::-1]:
            if i == 0:
                li[i] = 1
            else:
                li[i] = max(li[:i]) + 1
    print(max(li))



### FIXED CODE ###

for _ in range(int(input())):
    a = input()
    b = input()
    if len(a) < len(b):
        a, b = b, a
    indices = []
    for cb in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(indices):
            chr_idx = a.find(cb, bgn_idx) + 1
            if not chr_idx:
                break
            if chr_idx < cur_idx:
                indices[i] = chr_idx
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                indices.append(chr_idx)
    print(len(indices))
### BUGGY CODE ###

import queue
n,q = map(int,input().split())
c = [[] for _ in range(n)]
for i in range(n-1):
    A,B = map(int,input().split())
    c[A-1].append(B)
    c[B-1].append(A)
z = [0] * n
for i in range(q):
    P,X = map(int,input().split())
    z[P - 1] += X


d = [-1] * n
d[0] = 0
q = queue.Queue()
q.put(1)
while(not q.empty()):
    tp = q.get()
    td = d[tp - 1]
    for n2 in c[tp - 1]:
        if(d[n2 - 1] == -1):
            d[n2 - 1] = td + 1
            z[n2 - 1] += z[tp - 1]
            q.put(n2)

print(*z)

### FIXED CODE ###

from collections import deque
n,q = map(int,input().split())
c = [[] for _ in range(n)]
for i in range(n-1):
    A,B = map(int,input().split())
    c[A-1].append(B)
    c[B-1].append(A)
z = [0] * n
for i in range(q):
    P,X = map(int,input().split())
    z[P - 1] += X


d = [-1] * n
d[0] = 0
q = deque([])
q.append(1)
while(q):
    tp = q.popleft()
    td = d[tp - 1]
    for n2 in c[tp - 1]:
        if(d[n2 - 1] == -1):
            d[n2 - 1] = td + 1
            z[n2 - 1] += z[tp - 1]
            q.append(n2)

print(*z)
### BUGGY CODE ###

import sys
import numpy as np

def retmin(a, b):
    if a > b:
        return b
    return a

# N 足場の数、K カエルができる行動
n, k = map(int, input().split())

# H 各足場の高さ
h = list(map(int, input().split()))

# 初期化
# dp = np.full(100100, 1000000000)
dp = [999999999999 for i in range(100100)]
dp[0] = 0

for i in range(n):
    for j in range(k):
        if (i + j < n):
            c = abs(h[i+j]-h[i-1]) + dp[i-1]
            if (dp[i+j] > c):
                dp[i+j]  = c
print(int(dp[n-1]))

### FIXED CODE ###

import sys
import numpy as np

input = sys.stdin.readline

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

h = np.array([int(x) for x in input().split()])

# 初期化
dp = np.zeros(n, dtype=int)

for i in range(1, n):
    start = max(0, i-k)
    dp[i] = min(dp[start:i] + np.abs(h[i] - h[start:i]))
print(dp[n-1])
### BUGGY CODE ###

data_num = int(input())
price = list([0 for i in range(data_num)])
cnt = 0
deff_price = -999999999
for i in range(data_num):
    price[i] = int(input())

for i in range(data_num):
    for j in range(i+1,data_num):
        if price[j]-price[i]>deff_price:
            deff_price = price[j]-price[i]

print(str(deff_price))

### FIXED CODE ###

data_num = int(input())
cnt = 0
deff_price = -999999999
min_price = 0
tmp_price = 0

for i in range(data_num):
    price = int(input())
 
    if i ==0:
        min_price = price
    elif price - min_price > deff_price:
        deff_price = price - min_price
    
    if price < min_price:
        min_price = price

print(str(deff_price))
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = []
for i in range(1,n+1):
    ans.append(A.index(i)+1)

print(' '.join(map(str, ans)))


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
d = {}
for i,a in zip(range(1,n+1),A):
    d[a] = i
d = sorted(d.items())

for t in d:
    print (t[1], end=" ")
### BUGGY CODE ###

data = list(map(int, input().split()))
R = data[0]
G = data[1]
B = data[2]
N = data[3]

# R * a + G * b + B * c 

a = N // R + 1
b = N // G + 1
c = N // B + 1
res = 0

for Ri in range(a):
    if Ri * R > N:
        break
    for Gi in range(b):
        if Ri * R + Gi * G > N:
            break
        for Bi in range(c):
            if Ri * R + Gi * G + Bi * B > N:
                break
            if Ri * R + Gi * G + Bi * B == N:
                res = res + 1

print(res)


### FIXED CODE ###

data = list(map(int, input().split()))
R = data[0]
G = data[1]
B = data[2]
N = data[3]

# R * a + G * b + B * c 

a = N // R + 1
b = N // G + 1
# c = N // B + 1
res = 0

def check(Ri):
    global res
    Rx = Ri * R
    if Rx > N:
        return
    for Gi in range(b):
        Gx = Gi * G
        if Rx + Gx > N:
            break
        if (N - Rx - Gx) % B == 0:
            res = res + 1

[check(Ri) for Ri in range(a)]

print(res)
### BUGGY CODE ###

n,P = map(int,input().split())
#i = 2
from collections import defaultdict
dic = defaultdict(int)
# 約数分解
i = 2
N = P
while i*i <= N:
    if N%i != 0:
        continue
    num = 0
    while N%i == 0:
        num += 1
        N//=i
    dic[i] = num
if N != 1:
    dic[N] = 1
ans = 1
if n == 1:
    print(P)
else:
    for k,v in dic.items():
        #print(k*(v//n))
        if v//n >= 1:
            ans *= k * (v//n)
    print(ans)


### FIXED CODE ###

n,P = map(int,input().split())
#i = 2
from collections import defaultdict
dic = defaultdict(int)
# 約数分解
if n == 1:
    print(P)
    exit()
i = 2
N = P
while i*i <= N:
    #print(i,N)
    if N%i != 0:
        i += 1
        continue
    num = 0
    while N%i == 0:
        num += 1
        N//=i
    dic[i] = num
    i += 1
if N != 1:
    dic[N] = 1
ans = 1
for k,v in dic.items():
    if v//n >= 1:
        ans *= k ** (v//n)
print(ans)
### BUGGY CODE ###

N = int(input())
l = [int(x) for x in input().split()]
l.sort(reverse=True)
ans = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    a = l[j+1:]
    for x in range(len(a)):
      if l[i] < l[j] + a[x] and abs(l[j] - a[x]) < l[i]:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
from bisect import bisect_left
for i in range(n-2):
  for j in range(i+1, n-1):
    ab = l[i] + l[j]
    idx = bisect_left(l, ab)
    ans += max(idx-j-1, 0)
print(ans)
### BUGGY CODE ###

INF = 10 ** 12

N = int(input())
X = [0] * N
Y = [0] * N
P = [0] * N
for i in range(N):
    X[i], Y[i], P[i] = map(int,input().split())

score_X = []

for i in range(2 ** N):
    x = []
    I = i
    for j in range(N):
        i = I
        score = abs(X[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(X[j] - X[k]) * P[j])
            i >>= 1
        x.append(score)
    score_X.append(x)

score_Y = []

for i in range(2 ** N):
    y = []
    I = i
    for j in range(N):
        i = I
        score = abs(Y[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(Y[j] - Y[k]) * P[j])
            i >>= 1
        y.append(score)
    score_Y.append(y)

ans = [INF] * (N + 1)

for i in range(2 ** N):
    cnt = 0
    for j in range(N):
        if (i >> j) & 1:
            cnt += 1
    for j in range(i, -1, -1):
        j &= i
        score = 0
        for k in range(N):
            if not (i >> k) & 1:
                score += min(score_X[j][k], score_Y[i - j][k])
        ans[cnt] = min(ans[cnt], score)
    

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

### FIXED CODE ###

INF = 10 ** 12

N = int(input())
X = [0] * N
Y = [0] * N
P = [0] * N
for i in range(N):
    X[i], Y[i], P[i] = map(int,input().split())

score_X = []

for i in range(2 ** N):
    x = []
    I = i
    for j in range(N):
        i = I
        score = abs(X[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(X[j] - X[k]) * P[j])
            i >>= 1
        x.append(score)
    score_X.append(x)

score_Y = []

for i in range(2 ** N):
    y = []
    I = i
    for j in range(N):
        i = I
        score = abs(Y[j]) * P[j]
        for k in range(N):
            if i & 1:
                score = min(score, abs(Y[j] - Y[k]) * P[j])
            i >>= 1
        y.append(score)
    score_Y.append(y)

ans = [INF] * (N + 1)

for i in range(2 ** N):
    cnt = 0
    for j in range(N):
        if (i >> j) & 1:
            cnt += 1
    
    j = i
    
    while True:
        score = 0
        for k in range(N):
            if not (i >> k) & 1:
                score += min(score_X[j][k], score_Y[i - j][k])
        ans[cnt] = min(ans[cnt], score)
        if j == 0:
            break
        j = (j - 1) & i

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

n, m = map(int, input().split())
p = list(map(int, input().split()))
uf = [i for i in range(n + 1)]

def dfs(x):
    if uf[x] == x:
        return x
    return dfs(uf[x])

for _ in range(m):
    xy = list(map(int, input().split()))
    rx, ry = dfs(xy[0]), dfs(xy[1])
    if rx != ry:
        uf[rx] = ry
count = 0
for i in range(n):
    num = i + 1
    if p[i] == num or dfs(num) == dfs(p[i]):
        count += 1
print(count)

### FIXED CODE ###

n, m = map(int, input().split())
p = list(map(int, input().split()))
xys = [list(map(int, input().split())) for _ in range(m)]
mapp = [[] for _ in range(n + 1)]
for xy in xys:
    mapp[xy[0]].append(xy[1])
    mapp[xy[1]].append(xy[0])

bfs = [0] * (n + 1)
count = 0
for i in range(1, n + 1):
    nexts = mapp[i]
    if not(bfs[i]):
        bfs[i] = i
    for j in nexts:
        if bfs[j]:
            continue
        bfs[j] = i
        nexts += mapp[j]
    if bfs[i] == bfs[p[i - 1]]:
        count += 1
print(count)
### BUGGY CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
import time
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
#    n = 500
    cos = [min(i//n,n-1-i//n,i%n,n-1-i%n) for i in range(n**2)]
#    p = [i for i in range(n**2)]
    p = [int(i)-1 for i in ipt().split()]
    ans = 0
    hq = []
    dr = [-1,-n,1,n]
    al = [False]*(n**2)

    for pi in p:
        ans += cos[pi]
        hpq.heappush(hq,(cos[pi],pi))
        al[pi] = True
        while hq:
            qc,qi = hpq.heappop(hq)
            ad = qc if al[qi] else qc+1
            for d in dr:
                if 0 <= d+qi < n**2 and cos[d+qi] > ad:
                    hpq.heappush(hq,(ad,d+qi))
                    cos[d+qi] = ad
    print(ans)

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
import time
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
#    n = 500
    cos = [[min(i,j,n-1-i,n-1-j) for i in range(n)] for j in range(n)]
#    p = [(i//n,i%n) for i in range(n**2)]
    p = [((int(i)-1)//n,(int(i)-1)%n) for i in ipt().split()]
    ans = 0
    q = []
    al = [[True]*n for i in range(n)]

    for px,py in p:
        ans += cos[px][py]
        q.append((px,py,cos[px][py]))
        al[px][py] = False
        while q:
            qx,qy,qc = q.pop()
            if qx != 0 and cos[qx-1][qy] > qc:
                cos[qx-1][qy] = qc
                q.append((qx-1,qy,qc+al[qx-1][qy]))
            if qx != n-1 and cos[qx+1][qy] > qc:
                cos[qx+1][qy] = qc
                q.append((qx+1,qy,qc+al[qx+1][qy]))
            if qy != 0 and cos[qx][qy-1] > qc:
                cos[qx][qy-1] = qc
                q.append((qx,qy-1,qc+al[qx][qy-1]))
            if qy != n-1 and cos[qx][qy+1] > qc:
                cos[qx][qy+1] = qc
                q.append((qx,qy+1,qc+al[qx][qy+1]))

    print(ans)

    return

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

a, b, c, k = map(int, input().split())
A = [1 for _ in range(a)]
B = [0 for _ in range(b)]
C = [-1 for _ in range(c)]
D = A + B + C
p = 0
for i in range(k):
    p += D[i]
print(p) 

### FIXED CODE ###

a, b, c, k = map(int, input().split())
if k <= a:
    print(k)
if a < k <= a + b:
    print(a)
if a + b < k:
    d = 2*a + b - k
    print(d)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for ri in range(N//R+1):
  for gi in range(N//G+1):
    for bi in range(N//B+1):
      if ri*R+gi*G+bi*B==N:ans += 1
print(ans)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for ri in range(N//R+1):
  for gi in range(N//G+1):
    if (N-ri*R-gi*G)>=0 and (N-ri*R-gi*G)%B==0:ans += 1
print(ans)
### BUGGY CODE ###

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

t=0
v=2*n//k

for apb in range(k,k*(v+1),k):
  for bpc in range(k,k*(v+1),k):
    for cpa in range(k,k*(v+1),k):
      if (apb+bpc+cpa)%2:
        continue
      a = (apb+bpc+cpa - 2*bpc)//2
      b = (apb+bpc+cpa - 2*cpa)//2
      c = (apb+bpc+cpa - 2*apb)//2
      if 0 < a and a <= n and 0 < b and b<=n and 0 < c and c <= n:
        t += 1

print(t)


### FIXED CODE ###

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

x = n//k
y = x if k%2 else n//(k//2)

print(x**3+(y-x)**3)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n, a = map(int, input().split())
    x = tuple(map(int, input().split()))

    sm_mx = sum(x)

    dp = [[[0] * (sm_mx + 1) for i in range(n + 1)] for j in range(n + 1)]

    dp[0][0][0] = 1

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sm_mx + 1):
                if sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]

    ans = 0
    for i in range(1, n + 1):
        if i > sm_mx / a:
            break
        ans += dp[n][i][i*a]

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n, a = map(int, input().split())
    x = tuple(map(int, input().split()))

    sm_mx = sum(x)

    dp = [[[0] * (sm_mx + 1) for _ in range(n + 1)] for _ in range(n + 1)]

    dp[0][0][0] = 1

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sum(x[:i]) + 1):
                if sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]

    ans = 0
    for i in range(1, n + 1):
        if i > sm_mx / a:
            break
        ans += dp[n][i][i*a]

    print(ans)


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

N, K = map(int, input().split())
ans = 0
a = 1
while a <= N:
  b = K - a
  while b <= N:
    if b >=  1:
      c = K - a
      while c <= N:
        if c >= 1 and (b+c)%K == 0 and (c+a)%K == 0:
          ans += 1
        c += K
    b += K
  a += 1
print(ans)

### FIXED CODE ###

from collections import deque
N, K = map(int, input().split())
ans = (N // K)**3
if K % 2 == 0:
  m = K // 2
  cnt = 0
  i = m
  while i <= N:
    i += K
    cnt += 1
  ans += cnt**3
print(ans)
### BUGGY CODE ###

h,w = map(int,input().split())
c_h,c_w = map(int,input().split())
d_h,d_w = map(int,input().split())
s_list = [[c for c in input()] for _ in range(h)]

move_pattern = [[-1,0],[1,0],[0,-1],[0,1]]
around_area = [[i-2,j-2] for i in range(5) for j in range(5)]
kakutei_set = set([(c_h-1,c_w-1)])
temp_dic = {}
temp_dic[0] = set([(c_h-1,c_w-1)])
temp_num = 0
while True:
    cur_list = list(temp_dic[temp_num])
    for i,j in cur_list:
        for x,y in move_pattern:
            if i+y<0 or i+y>=h or j+x<0 or j+x>=w:
                continue
            elif s_list[i+y][j+x]=="#":
                continue
            elif (i+y,j+x) in kakutei_set:
                continue
            else:
                cur_list.append((i+y,j+x))
                temp_dic[temp_num].add((i+y,j+x))
                kakutei_set.add((i+y,j+x))
    temp_dic[temp_num+1] = set()
    for i,j in temp_dic[temp_num]:
        for x,y in around_area:
            if i+y<0 or i+y>=h or j+x<0 or j+x>=w:
                continue
            elif s_list[i+y][j+x]=="#":
                continue
            elif (i+y,j+x) in kakutei_set:
                continue
            else:
                temp_dic[temp_num+1].add((i+y,j+x))
                kakutei_set.add((i+y,j+x))
    temp_num += 1
    if len(temp_dic[temp_num])==0:
        break
if (d_h-1,d_w-1) not in kakutei_set:
    print(-1)
else:
    for key,value in temp_dic.items():
        if (d_h-1,d_w-1) in value:
            print(key)

### FIXED CODE ###

h,w = map(int,input().split())
c_h,c_w = map(int,input().split())
d_h,d_w = map(int,input().split())
s_list = [[c for c in input()] for _ in range(h)]

move_pattern = [[-1,0],[1,0],[0,-1],[0,1]]
around_area = [[i-2,j-2] for i in range(5) for j in range(5)]
kakutei_set = set([(c_h-1,c_w-1)])
temp_dic = {}
temp_dic[0] = set([(c_h-1,c_w-1)])
temp_num = 0
while True:
    cur_list = list(temp_dic[temp_num])
    for i,j in cur_list:
        for x,y in move_pattern:
            if i+y<0 or i+y>=h or j+x<0 or j+x>=w:
                continue
            elif s_list[i+y][j+x]=="#":
                continue
            elif (i+y,j+x) in kakutei_set:
                continue
            else:
                cur_list.append((i+y,j+x))
                temp_dic[temp_num].add((i+y,j+x))
                kakutei_set.add((i+y,j+x))
    temp_dic[temp_num+1] = set()
    for i,j in temp_dic[temp_num]:
        for x,y in around_area:
            if i+y<0 or i+y>=h or j+x<0 or j+x>=w:
                continue
            elif s_list[i+y][j+x]=="#":
                continue
            elif (i+y,j+x) in kakutei_set:
                continue
            else:
                temp_dic[temp_num+1].add((i+y,j+x))
                kakutei_set.add((i+y,j+x))
    temp_num += 1
    if len(temp_dic[temp_num])==0:
        break
if (d_h-1,d_w-1) not in kakutei_set:
    print(-1)
else:
    for key,value in temp_dic.items():
        if (d_h-1,d_w-1) in value:
            print(key)
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]

A1 = [0]*N
A2 = [0]*N

for i in range(N):
    A1[i] = A[i] + (i+1)

for j in range(N):
    A2[j] = (j+1) - A[j]

cnt = 0
for i in range(N):
    cnt += A2[i:].count(A1[i])

print(cnt)

### FIXED CODE ###

from collections import Counter
# import sys

# input = sys.stdin.readline

N = int(input())
A = [int(a) for a in input().split()]

A1 = [0]*N
A2 = [0]*N

for i in range(N):
    A1[i] = A[i] + i
    A2[i] = i - A[i]

c = Counter(A2)

cnt = 0
for i in range(N):
    cnt += c[A1[i]]

print(cnt)