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

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

if n%2 == 0:
    for i in range(1,n,2):
        if not A.count(i) == 2:
            print(0)
            break
    else:
        print(2**(n//2)%(10**9+7))
else:
    if not A.count(0) == 1:
        print(0)
    else:
        for i in range(2,n,2):
            if not A.count(i) == 2:
                print(0)
                break
        else:
            print(2**((n-1)//2)%(10**9+7))

### FIXED CODE ###

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

if n%2 == 0:
    for i in range(n):
        if i%2 == 0:
            if not A[i] == i+1:
                print(0)
                break
        else:
            if not A[i] == i:
                print(0)
                break
    else:
        print(2**(n//2)%(10**9+7))
else:
    if not A[0] == 0:
        print(0)
    else:    
        for i in range(1,n):
            if i%2 == 0:
                if not A[i] == i:
                    print(0)
                    break
            else:
                if not A[i] == i+1:
                    print(0)
                    break
        else:
            print(2**((n-1)//2)%(10**9+7))
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    init = list(input().split())
    if init[0] == '1':
        s = s[::-1]
    else:
        c = init[2]
        if init[1] == '1':
            s = c + s
        else:
            s = s + c
str = ''.join(s)
print(str)


### FIXED CODE ###

s = input()
q = int(input())
a = []
b = []
c = 0
for i in range(q):
    init = list(input().split())
    if init[0] == '1':
        a, b = b, a
        c += 1
    else:
        if init[1] == '1':
            a.append(init[2])
        else:
            b.append(init[2])
if c % 2 == 1:
    s = s[::-1]
print(''.join(a[::-1]) + s + ''.join(b))
### BUGGY CODE ###

n=int(input()) 
c = 0
tmp = 0

for i in range(3234566668):
    if i != 0:
        s = str(i)
        if len(s) != 1:
            for j in range(len(s)-1):
                if int(s[j]) > int(s[j+1]):
                    a = int(s[j]) - int(s[j+1])
                else:
                    a = int(s[j+1]) - int(s[j])
                if a > 1:
                    tmp = 0
                    break
                tmp = 1
        else:
            tmp = 1

        if tmp == 1:
            c = c + 1
        if c == n:
            print(i)
            exit()

### FIXED CODE ###

from collections import deque
k=int(input())

q = deque([1,2,3,4,5,6,7,8,9])
ans = 0
flg = 0
cnt = 0

while(flg != 1):
    ans = q.popleft()
    cnt += 1

    tmp = ans % 10
    if tmp != 0:
        q.append(ans * 10 + tmp - 1)
    
    q.append(ans * 10 + tmp)
    
    if tmp != 9:
        q.append(ans * 10 + tmp + 1)

    if cnt == k:
        print(ans)
        flg = 1
### BUGGY CODE ###

n ,m = map(int, input().split())
result = set()
first = True
for i in range(m):
    l, r = map(int, input().split())
    tmp = set()
    for i in range(l, r + 1):
        tmp.add(i)
    if first:
        result = tmp
        # print("tmp {}".format(tmp))
        first = False
    else:
        result = result.intersection(tmp)
        # print("result {} tmp {}".format(result, tmp))

print(len(result))

### FIXED CODE ###

n ,m = map(int, input().split())
L = []
R = []
for i in range(m):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
if max(L) <= min(R):
    print(min(R) - max(L) + 1)
else:
    print(0)
### BUGGY CODE ###

"""
https://atcoder.jp/contests/dp/tasks/dp_j
"""
from sys import stdin
from collections import defaultdict
input = stdin.readline

n = int(input())
c = [0] * 4
l = list(map(int, input().split()))

for i in l:
    c[i] += 1

dp = defaultdict(int)
dp[(0, 0, 0)] = 0
for n3 in range(0, c[3] + 1):
    for n2 in range(0, c[2] + c[3] - n3 + 1):
        for n1 in range(0, n - c[0] - n2 - n3 + 1):
            s = n1 + n2 + n3
            if s != 0:
                temp = n
                if n1 != 0:
                    temp += n1 * dp[(n1 - 1, n2, n3)]
                if n2 != 0:
                    temp += n2 * dp[(n1 + 1, n2 - 1, n3)]
                if n3 != 0:
                    temp += n3 * dp[(n1, n2 + 1, n3 - 1)]
                temp /= s
                dp[(n1, n2, n3)] = temp

print(dp[(c[1], c[2], c[3])])


### FIXED CODE ###

"""
https://atcoder.jp/contests/dp/tasks/dp_j
"""
from sys import stdin
input = stdin.readline

n = int(input())
c = [0] * 4
l = list(map(int, input().split()))

for i in l:
    c[i] += 1

dp = [[[0.0] * (n + 1) for i in range(n + 1)] for j in range(n + 1)]
dp[0][0][0] = 0
for n3 in range(0, c[3] + 1):
    for n2 in range(0, c[2] + c[3] - n3 + 1):
        for n1 in range(0, n-c[0]- n3 - n2 + 1):
            if n1 == n2 == n3 == 0:
                continue
            temp = n
            if n1 != 0:
                # temp += n1 * dp[(n1 - 1, n2, n3)]
                temp += n1*dp[n1 - 1][n2][n3]
            if n2 != 0:
                # temp += n2 * dp[(n1 + 1, n2 - 1, n3)]
                temp += n2*dp[n1 + 1][n2 - 1][n3]
            if n3 != 0:
                # temp += n3 * dp[(n1, n2 + 1, n3 - 1)]
                temp += n3*dp[n1][n2 + 1][n3 - 1]
            dp[n1][n2][n3] = temp / (n1 + n2 + n3)

print(dp[c[1]][c[2]][c[3]])
### BUGGY CODE ###

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

ans = 0
for j in range(max(p)):
    agc = [i for i in p if i>j]
    if len(agc) == len(p)-len(agc):
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
p = list(map(int,input().split()))
p = sorted(p)
c = p[N//2-1]
d = p[N//2]
print(d-c)
### BUGGY CODE ###

import sys
from itertools import combinations

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split(" ")))

    res = 0
    for i, j in combinations(A, 2):
        res += (i * j)
    print(res % (10 ** 9 + 7))
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
 
def main():
    def input():return sys.stdin.readline()[:-1]
    N = int(input())
    A = list(map(int, input().split(" ")))
 
    mod = 10**9+7
    res = 0

    S = sum(A)
    S2 = sum(map(lambda x: x**2, A))
    print((S**2-S2) // 2 % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

K,S=map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                count+=1
print(count)

### FIXED CODE ###

K,S=map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        if 0<=S-x-y<=K:
            count+=1
print(count)
### BUGGY CODE ###

N = int(input())
a = [int(input()) for i in range(N)]
A = max(a)
for i in range(len(a)):
    if i == a.index(A):
        print(sorted(a)[-2])
    else:
        print(A)

### FIXED CODE ###

N = int(input())
a = [int(input()) for i in range(N)]
A = max(a)
b = sorted(a)[-2]
if a.count(A) > 1:
    for i in range(len(a)):
        print(A)
else:
    for i in range(len(a)):
        if a[i] == A:
            print(b)
        else:
            print(A)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from itertools import combinations

MOD = 2  # type: int


def solve(N: int, P: int, A: "List[int]"):
    c = 0
    for i in range(N+1):
        for com in combinations(A, i):
            if sum(com) % 2 == P:
                c += 1
    print(c)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import combinations

MOD = 2  # type: int


def solve(N: int, P: int, A: "List[int]"):
    if all(map(lambda a: a % 2 == 0, A)):
        print(2 ** N if P == 0 else 0)
        return
    print(2 ** (N-1))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P, A)

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

def main():
    n, q = map(int, input().split())
    t = [[] for _ in range(n)]
    r = [0]*n
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        t[a].append(b)
        t[b].append(a) # leafの順序が保証されないため双方向にリンクを設定
    # root(t[0])からleafまで親ノードのリンクを消しながら辿る
    e = [0]
    while len(e) > 0:
        i = e.pop()
        for j in t[i]:
            t[j].remove(i)
            e.append(j)
    #print("tree", t)
    
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        r[p] += x
        s = t[p][:]
        while len(s) > 0:
            #print("next", s)
            #print("end", e)
            i = s.pop()
            r[i] += x
            s.extend(t[i])
        #print(">>", *r)
    print(*r)
            
        
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n,q=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in range(n-1)]
    tree=[list() for _ in range(n)]
    score=[0]*n
    for a,b in ab:
        a,b=a-1,b-1
        tree[a].append(b)
        tree[b].append(a)
    e = [0]
    while len(e) > 0:
        i = e.pop()
        for j in tree[i]:
            tree[j].remove(i)
            e.append(j)
    px=[list(map(int,input().split())) for _ in range(q)]
    for p,x in px:
        p-=1
        score[p]+=x
    add(tree,score)
    print(*score)

def add(tree,score):
    s=tree[0][:]
    for i in s:
        score[i] += score[0]
    while len(s)>0:
        t = s.pop()
        for i in tree[t]:
            s.append(i)
            score[i] += score[t]

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

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

for i in range(n[0]):
    p[i]=(p[i]+1)/2
y=[]
for i in range(n[0]-n[1]+2):
    y.append(sum(p[i:i+n[1]]))
print(max(y))

### FIXED CODE ###

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

for i in range(n):
    p[i]=(p[i]+1)/2#p[i]を期待値に変更
    
p_sum=[0]*n
ans=0
for i in range(n):
    if i==0:
        p_sum[i]=p[i]
        ans=p_sum[i]
    elif i<k:
        p_sum[i]=p_sum[i-1]+p[i]
        if p_sum[i]>ans:
            ans=p_sum[i]
    else:
        p_sum[i]=p_sum[i-1]+p[i]-p[i-k]
        if p_sum[i]>ans:
            ans=p_sum[i]
print(ans)
### BUGGY CODE ###

s = input()

res = 0

if len(s) <= 3:
    print(res)
else:
    for i in range(len(s) - 3):
        for j in range(i + 4, len(s) + 1):
            if int(s[i:j]) % 2019 == 0:
                res += 1
    
    print(res)

### FIXED CODE ###

N = 2019
cnt = [0] * N
S = input()
ans = 0
for s in S:
    s = int(s)
    new = [0] * N
    for n in range(N):
        idx = (10 * n + s) % N
        new[idx] += cnt[n]
    cnt = new
    cnt[s] += 1
    ans += cnt[0]
print (ans)
### BUGGY CODE ###

n = int(input())
l = []
l[:] = map(int,input().split())
l.sort()

c = 0
for i in range(0,n-2):
    for j in range(i+1, n-1):
        ab = l[i]+l[j]
        for k in range(j+1, n):
            if(ab>l[k]):
                c+=1
            else:
                continue
print(c)


### FIXED CODE ###

from bisect import bisect_right

n = int(input())
l = list(map(int,input().split()))
l.sort() # 昇順にソート

count = 0
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1, n-1):
        ab = a+l[j]
        # bisect_left(a, x): x を a に挿入できる点を返す
        # cの最大値は a+b-1
        k = bisect_right(l, ab-1, j+1, n)
        count += k-(j+1)
print(count)
### BUGGY CODE ###

import math
n, m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]
a.append(n+1)
func = math.factorial
count = 1
for i in range(m+1):
    k = a[i+1] - a[i] - 2
    if k == -1:
        count = 0
        break
    else:
        work = 0
        for b in range(k//2+1):
            work += func(k-b)//(func(k-2*b)*func(b))
        count *= work
print(count%1000000007)

### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(100000)
f = math.factorial
n, m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


count = 1
for i in range(m+1):
    k = a[i+1] - a[i] - 2
    if k == -1:
        count = 0
        break
    else:
        work = 0
        for b in range(k//2+1):
            work += cmb(k-b, b, p)
        count *= work
print(count%p)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
cand_1 = []
cand_2 = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cand_1.append(b)
    elif b == N:
        cand_2.append(a)

ans = "IMPOSSIBLE"
for i in cand_1:
    for j in cand_2:
        if i == j:
            ans = "POSSIBLE"
            break
print(ans)


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
cand_1 = []
cand_2 = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cand_1.append(b)
    elif b == N:
        cand_2.append(a)

ans = "IMPOSSIBLE"
heapq.heapify(cand_1)
heapq.heapify(cand_2)


while len(cand_1) != 0 and len(cand_2) != 0:
    if cand_1[0] < cand_2[0]:
        heapq.heappop(cand_1)
    elif cand_1[0] > cand_2[0]:
        heapq.heappop(cand_2)
    else:
        ans = "POSSIBLE"
        break
print(ans)
### BUGGY CODE ###

import sys

N = int(input())

max = 0
for _ in range(1,N):
    max = max + _
print(max)


### FIXED CODE ###

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

n, k = map(int, input().split())
cnt = 0
while True:
    cnt += 1
    if k**cnt <= n and n < k**(cnt+1):
        print(cnt+1)
        break

### FIXED CODE ###

n, k = map(int, input().split())
for i in range(n):
    if k**i <= n and n < k**(i+1):
        print(i+1)
        break
### BUGGY CODE ###

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

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
A = 10**12
B = 10**6
d = [INF] * (h*w)

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

T = ((-1,0), (1,0), (0,1), (0,-1))

q = [(ch-1)*A + (cw-1)*B + 0]
for x in q:
    curh = (x // A)
    x -= curh * A
    curw = (x // B)
    cnt = x - curw * B

    if d[curh * w + curw] <= cnt: continue
    else:
        d[curh * w + curw] = cnt

    for dh, dw in T:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            q.append(nh*A + nw*B + cnt)

    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            q.append(nh*A + nw*B + cnt+1)

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])


### FIXED CODE ###

import heapq
class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

S = [input() for _ in range(h)]

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)
### BUGGY CODE ###

a,b,x=map(int,input().split())
for i in range(a,b+1):
  if i%x==0:
    y=(b-i)//x
    print(y+1)
    exit()

print(0)

### FIXED CODE ###

a,b,x=map(int,input().split())
bb=b//x
aa=a//x
ans=bb-aa
if a%x==0:
  ans+=1
print(ans)
### BUGGY CODE ###

import math
k, s = map(int, input().split())
count=0
if k < s/3:
  print(0)
  quit()
for a in range(0, k+1):
  if a == s:
    print(count+1)
    quit()
  for b in range(0, k+1):
    if a+b == s:
      count+=1
      break
    elif a+b > s:
      break
    for c in range(0, k+1):
      if a+b+c == s:
        count+=1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count=0
for a in range(0, k+1):
  for b in range(0, k+1):
    if s-a-b >= 0 and s-a-b <= k:
      count+=1
print(count)
### BUGGY CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a=( a+all ) %M
	if x=="B":
		ab=( ab+a )%M
	if x=="C":
		abc=( abc+ab )%M

	if x=="?":
		abc=( abc*3+ab )%M
		ab=( ab*3+a)%M
		a=( a*3+all )%M
		all*=3

print abc%M


### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

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

dp = [0] + [float("inf")]*(n-1)
dp[0] = 0
for i in range(1,n):
    for j in range(max(0,i-k), i):
        dp[i] = min( dp[i], dp[j]+abs(h[i]-h[j]) )
print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

dp = [0] + [float("inf")]*(n-1)
dp[0] = 0
for i in range(1,n):
    for j in range(max(0,i-k), i):
        dp[i] = min( dp[i], dp[j]+abs(h[i]-h[j]) )
print(dp[-1])
### BUGGY CODE ###

from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*50*M
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:M]:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

### FIXED CODE ###

from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in range(M)]
for i in range(N):
	if t[2*i]<=M:
		v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in range(M):
	for j in v[i]:
		heappush(q,-j)
	b=0
	if len(q):
		b=heappop(q)
	z-=b
print(z)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

N = int(input())
MOD = 10 ** 9 + 7

to = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)

visited = [False] * N
def dfs(n):
    visited[n] = True
    w = 1
    b = 1
    for i in to[n]:
        if visited[i] == False:
            rw, rb = dfs(i)
            w *= rw + rb
            b *= rw
    w %= MOD
    b %= MOD
    return (w,b)

ans = dfs(0)
print((ans[0] + ans[1]) % MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

N = int(input())
MOD = 10 ** 9 + 7

to = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)

def dfs(n,p):
    w = 1
    b = 1
    for i in to[n]:
        if i != p:
            rw, rb = dfs(i, n)
            w *= (rw + rb)
            w %= MOD
            b *= rw
            b %= MOD
    return (w,b)

ans = dfs(0, -1)
print((ans[0] + ans[1]) % MOD)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
max_a = max(a)
ans = 0
for i in range(n - 1):
    if a[i] == max_a:
        max_a = max(a[i + 1:])
    for j in range(a[i] + i + 1, min(n, a[i] + i + max_a + 1)):
        if a[i] + a[j] == j - i:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [0] * n
ans = 0
for i, j in enumerate(a):
    if i + j < n:
        dp[i + j] += 1
    if 0 < i - j:
        ans += dp[i - j]
print(ans)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 998244353

n, k = map(int, input().split())
s = set()
for _ in range(k):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        s.add(i)

dp = [0] * (n + 1)
dp[0] = 1

for i in range(1, n + 1):
    for j in range(i):
        if i - j in s:
            dp[i] += dp[j]
            dp[i] %= mod

print(dp[-2])
    

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 998244353

n, k = map(int, input().split())
l = []
r = []
for _ in range(k):
    l_, r_ = map(int, input().split())
    l.append(l_)
    r.append(r_)
dp = [0] * (n + 1)
dp_csum = [0] * (n + 1)
dp[1] = 1
dp_csum[1] = 1
for i in range(2, n + 1):
    for j in range(k):
        left = i - r[j]
        right = i - l[j]
        if right >= 1:
            dp[i] += dp_csum[right] - dp_csum[max(left, 1) - 1]
            dp[i] %= mod
    dp_csum[i] = dp_csum[i - 1] + dp[i]
    dp_csum[i] %= mod
print(dp[-1])
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = sorted(list(map(int, input().split())), reverse=True)
    C = sorted(list(map(int, input().split())))

    ans = 0
    for a in A:
        for b in B:
            if a >= b:
                break
            for i, c in enumerate(C):
                if c > b:
                    ans += N - i
                    break
    print(ans)


main()


### FIXED CODE ###

import bisect


def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    C = sorted(list(map(int, input().split())))

    ans = 0
    for b in B:
        ans += bisect.bisect_left(A, b) * (N - bisect.bisect_right(C, b))
    print(ans)


main()
### BUGGY CODE ###

A, B, N = [int(i) for i in input().split()]

def floor(A: int, B: int, x: int) -> int:
    return (A * x) // B - A * (x // B)

print(max(floor(A, B, n) for n in range(N + 1)))


### FIXED CODE ###

A, B, N = [int(i) for i in input().split()]

def f(x: int) -> int:
    return (A * x) // B - A * (x // B)

x = min(N, B - 1)
print(f(x))