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

MOD = 1000000007
N = int(input())
A = sorted(list(map(int,input().split())))
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        ans += A[i]^A[j]
        ans %= MOD
print(ans%MOD)

### FIXED CODE ###

MOD = 1000000007

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

def sumXOR(arr,n):
    xorsum = 0
    for i in range(64):
        zc = 0
        oc = 0
        idsum = 0
        for j in range(n):
            if arr[j] % 2 == 0:
                zc += 1
            else:
                oc += 1
            arr[j] = arr[j]//2
        idsum = oc*zc*(1 << i)
        xorsum += idsum
        xorsum %= MOD
    return xorsum

XORSUM = 0
XORSUM = sumXOR(A,N);
print(XORSUM%MOD)
### BUGGY CODE ###

ignore = int(raw_input())
k = map(int, raw_input().split())
copyk = list(set(k))
counter = 0


for i in range(len(copyk)):
    while(k.count(copyk[i]) > copyk[i]):
        k.remove(copyk[i])
        counter += 1
    if k.count(copyk[i]) < copyk[i]:
        while(copyk[i] in k):
            k.remove(copyk[i])
            counter += 1


print counter


### FIXED CODE ###

from collections import Counter

ignore = int(raw_input())
k = dict(Counter(map(int, raw_input().split())))
copyk = list(set(k))
counter = 0
for i,j in k.items():
    if i > j:
        counter += j
    elif i < j:
        counter += j - i

print counter
### BUGGY CODE ###

n = int(input())
t = []
m = 0

for i in range(n):
    s = list(input())
    s.sort()
    t.append(s)
    
for i in range(n):
    for j in range(n - i - 1):
        if t[i] == t[j + i + 1]:
            m += 1
        
print(m)

### FIXED CODE ###

n = int(input())
d = {}
ans = 0
for _ in range(n):
    s = list(input())
    s.sort()
    s = "".join(s)
    if s in d:
        d[s] += 1
        ans += d[s]
    else:
        d.update({s : 0})
print(ans)
### BUGGY CODE ###

# %%
N,K = map(int ,input().split(" "))
list1 = []

#差分して絶対値を求める関数
def abs_ded(A,B):
    return abs(A-B)

#繰り返して、リストに代入していく関数
def make_list(A,B):
    list1.append(abs_ded(A,B))
    while 1:
        key = abs_ded(list1[-1],B)
        if key <= B:
            if key >= list1[-1]:
                answer = list1[-1]
                break
            else:
                list1.append(key)
    
    print(answer)

make_list(N,K)

### FIXED CODE ###

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

a = N % K
b = K - a

if(a>b):
    print(b)
else:
    print(a)
### BUGGY CODE ###

import heapq

INF = float('inf')

N = int(input())
to = [[] for _ in range(N)]

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

Q, K = map(int, input().split())
query = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(Q)]


def dijkstra(s, e):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [INF] * N # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in to[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost[e]


def main():
    for x, y in query:
        print(dijkstra(x, K - 1) + dijkstra(y, K - 1))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)


N = int(input())
to = [[] for _ in range(N)]

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

Q, K = map(int, input().split())
K -= 1
query = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(Q)]
depth = [0] * N

def dfs(v, d, p=-1):
    depth[v] = d
    for cost, nv in to[v]:
        if nv == p:
            continue
        dfs(nv, d + cost, v)


def main():
    dfs(K, 0)
    for x, y in query:
        print(depth[x] + depth[y])


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

def kouyakusuuset(x,y):
    lst=set()
    for i in range(1,x+1):
     if x%i==0 and y%i==0:
         lst.add(i)
    return(lst)


A,B=map(int,input().split())
lst=kouyakusuuset(A,B)
lst=list(lst)
#print(lst)
data=[1 for i in lst]
count=0
for i in range(1,len(lst)-1):
    for m in range(i+1,len(lst)):
        if len(kouyakusuuset(lst[i],lst[m]))>=2:
            data[m]=0
#print(data)
print(len([i for i in data if i]))


### FIXED CODE ###

A,B=map(int,input().split())
lst=set()
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

if A==B==1:
    print(1)
else:
    print(len(set([i[0] for i in factorization(A)])&set([i[0] for i in factorization(B)]))+1)
### BUGGY CODE ###

import bisect
from itertools import accumulate

n = int(input())
s = input()
a_loc = []
b_loc = []
c_acc = [0] * (n + 1)
c_cnt = 0
for i, c in enumerate(s):
    if c == 'D':
        a_loc.append(i)
    elif c == 'M':
        b_loc.append(i)
    elif c == 'C':
        c_cnt += 1
    c_acc[i + 1] = c_cnt

ri = bisect.bisect(a_loc, b_loc[-1])
q = int(input())
b_acc = [0] + list(accumulate(c_acc[b] for b in b_loc))
buf = []
for k in map(int, input().split()):
    ans = 0
    pi = 0
    for a in a_loc[:ri]:
        i = bisect.bisect(b_loc, a, pi)
        j = bisect.bisect(b_loc, a + k - 1, i)
        ans += c_acc[min(n, a + k)] * (j - i) - (b_acc[j] - b_acc[i])
        pi = i
    buf.append(ans)
print('\n'.join(map(str, buf)))


### FIXED CODE ###

from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))
### BUGGY CODE ###

n = int(input())
a = list(map(int, list(input())))

b = ''
for ai in range(len(a)):
  b += '1'

bi = int(b, 2)
del_num = n - 3

kinds = []
for i in range(bi):
  bin_list = list(format(i, '0'+str(len(a))+'b'))
  if bin_list.count('0') != del_num:
    continue
  k = ''
  for index, s in enumerate(bin_list):
    if s == '1':
      k += str(a[index])
  kinds.append(k)

print(len(set(kinds)))
  

### FIXED CODE ###

n = int(input())
a = input()

r = 0
for i in range(10):
  s = a.find(str(i))
  if s == -1:
    continue
  for j in range(10):
    s2 = a.find(str(j), s + 1)
    if s2 == -1:
      continue
    for k in range(10):
      if a.find(str(k), s2 + 1) != -1:
        r += 1
print(r)
### BUGGY CODE ###

n = int(input())
count = 0
for x in range(1, n):
  for y in range(x + 1, n):
    if x + y == n:
      count += 1
print(count)

### FIXED CODE ###

n = int(input())

if n % 2 == 0:
  print(n // 2 - 1)
else:
  print((n - 1) // 2)
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(list(str(input())))
    
cnt = 0
for i in range(n-1):
    for j in range(i+1, n):
        if sorted(s[i]) == sorted(s[j]):
            cnt+=1

print(cnt)

### FIXED CODE ###

n = int(input())
ss = ["".join(sorted(list(input()))) for _ in range(n)]
ss.sort()

ans = 0
cnt = 0
tmp = ss.pop(0)
for s in ss:
    if tmp == s:
        cnt+=1
    elif cnt > 0:
        tmp = s
        ans+=((cnt+1) * cnt // 2)
        cnt = 0
    else:
        tmp = s
        cnt = 0
print(ans + ((cnt+1) * cnt // 2))
### BUGGY CODE ###

import sys
import numpy as np
from fractions import gcd
from functools import reduce

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

input()
A = list(map(int, input().split()))
lcm = lcm_list(A)

print((lcm // np.array(A, dtype=np.int64)).sum() % LARGE)


### FIXED CODE ###

import sys
from fractions import gcd

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

def lcm(x, y):
    return (x * y) // gcd(x, y)

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

l = 1
for a in A:
    l = lcm(l, a)

total = 0
for a in A:
    total += l // a

print(total % LARGE)
### BUGGY CODE ###

import copy
from statistics import median


N = int(input())

X = input().split()
X = [ int(x) for x in X]
"""
N = 4
X = [2,4,4,3]
"""
j = int(N/2)

for i in range(N):
    F = copy.deepcopy(X)
    del F[i]
#    F.sort()
    print(median(F))
    

### FIXED CODE ###

from statistics import median, median_low, median_high


N = int(input())

X = input().split()
X = [ int(x) for x in X]
"""
N = 4
X = [2,4,4,3]
"""
median = median(X)
#F = copy.deepcopy(X)
"""
F = X[:]
F.sort()

median1 = int(N/2 - 1)
median2 = int(N/2) 

if median.is_integer():
    median1 = median
    median2 = median
else:
    median1 = median - 0.5
    median2 = median + 0.5
"""
median1 = median_low(X)
median2 = median_high(X)
   
for i in range(N):
    #print(F, median1, median2)
    
    if X[i] < median:
        ans = median2
    else:
        ans = median1
    print(int(ans))
### BUGGY CODE ###

n=int(input())
an=[]
an=[int(input()) for i in range(n)]
for i in range(n):
    an_a=an[0:i]+an[i+1:n]
    print(max(an_a))

### FIXED CODE ###

n=int(input())
an=[]
an=[int(input()) for i in range(n)]
s_an=sorted(an,reverse=True)
m_an=max(an)
m_an2=s_an[1]
for i in an:
    if m_an==i:
        print(m_an2)
    else:
        print(m_an)
### BUGGY CODE ###

N,M=map(int,input().split())
bridges = [1]*N
islandswar = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    islandswar[b].append(a)
count = 0

def check(a,b):
    for i in range(a,b):
        if bridges[i] == 0:
            return False
    return True
    

for i in range(2,N+1):
    for j in range(0,len(islandswar[i])):
        if check(islandswar[i][j],i):
            bridges[i-1] = 0
            count += 1

print(count)

### FIXED CODE ###

N,M=map(int,input().split())
bridges = [1]*N
islandswar = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    islandswar[b].append(a)
count = 0
currightest = 0

def check(a,b):
    for i in range(a,b):
        if bridges[i] == 0:
            return False
    return True
    

for i in range(2,N+1):
    for j in range(0,len(islandswar[i])):
        if islandswar[i][j] >= currightest:
            if check(islandswar[i][j],i):
                bridges[i-1] = 0
                currightest = i
                count += 1

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

from itertools import product

INF = float("inf")

H, W, K = map(int, input().split())
S = [[int(i) for i in input()] for _ in range(H)]

T = [t for t in zip(*S)]
if sum(map(sum, T)) <= K:
    print(0)
    quit()

ans = INF
for P in product([0, 1], repeat=H - 1):
    cnt = sum(P)

    II = [[0]]
    for i, p in enumerate(P, 1):
        if p:
            II.append([])
        II[-1].append(i)

    A = [0] * len(II)
    for t in T:
        for i, I in enumerate(II):
            A[i] += sum(t[x] for x in I)

        if any(a > K for a in A):
            cnt += 1
            if cnt >= ans:
                break

            A = [sum(t[x] for x in I) for I in II]
            if any(a > K for a in A):
              cnt = INF
              break

    ans = min(ans, cnt)

print(ans)

### FIXED CODE ###

from itertools import product

H, W, K = map(int, input().split())
S = [[int(i) for i in input()] for _ in range(H)]

T = [t for t in zip(*S)]
if sum(map(sum, T)) <= K:
    print(0)
    quit()

ans = float("inf")
for P in product([0, 1], repeat=H - 1):
    cnt = sum(P)
    if cnt >= ans:
        continue

    II = [[0]]
    for i, p in enumerate(P, 1):
        if p:
            II.append([])
        II[-1].append(i)

    A = [0] * len(II)
    for t in T:
        for i, I in enumerate(II):
            A[i] += sum(t[x] for x in I)

        if any(a > K for a in A):
            cnt += 1
            if cnt >= ans:
                break

            A = [sum(t[x] for x in I) for I in II]
            if any(a > K for a in A):
              cnt = 1 + ans
              break

    ans = min(ans, cnt)

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

from collections import deque

X, K, D = map(int, input().split())

# loopに入ったらおしまい
record = deque([X,])
finished = False
while K > 0:
    if X > 0:
        X -= D
    else:
        X += D
    record.append(X)
    if len(record) > 3:
        record.popleft()
    if record[0] == record[-1]:
        if K % 2 == 0:
            print(abs(record[1]))
        else:
            print(abs(record[0]))
        finished = True
        break
    K -= 1     

if not finished:
    print(abs(X))


### FIXED CODE ###

from collections import deque

X, K, D = map(int, input().split())

# まずは何回目で符号が逆転するかを算出
num_reverse = abs(X) // D + 1
if num_reverse > K:
    print(abs(X) - (K * D))
else:
    K -= num_reverse
    ans = abs(X) - (num_reverse * D)
    if K % 2 == 0:
        print(abs(ans))
    else:
        print(abs(abs(ans) - D))
### BUGGY CODE ###

N, K = map(int, input().split())
dp = [0] * N
dp[0] = 1
L = [0] * K
R = [0] * K
mod = 998244353

for i in range(K):
    l, r = map(int, input().split())
    L[i] = l
    R[i] = r

for i in range(1, N):
    # マスiにたどり着くためのパターン数を数える
    cnt = 0
    for j in range(K):
        for k in range(L[j], R[j] + 1):
            if i - k >= 0:
                cnt += dp[i - k]
                cnt %= 998244353
    dp[i] = cnt

print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
dp = [0] * N
dp[0] = 1
dp_sum = [0] * N
dp_sum[0] = 1
L = [0] * K
R = [0] * K
mod = 998244353

for i in range(K):
    l, r = map(int, input().split())
    L[i] = l
    R[i] = r

for i in range(1, N):
    # マスiにたどり着くためのパターン数を数える
    cnt = 0
    for j in range(K):
        start = max(0, i - R[j])
        end = i - L[j]
        cnt += (dp_sum[end] - dp_sum[start - 1]) % mod
        cnt %= mod
    dp[i] = cnt
    dp_sum[i] = dp_sum[i - 1] + cnt

print(dp[N - 1])
### BUGGY CODE ###

n,k = map(int,input().split())
key = []
value = []
a, b = map(int, input().split())
key.append(a)
value.append(b)
s = 0
for i in range(n-1):
    last = True    
    a, b = map(int, input().split())
    for j in range(len(key)):
        if a <= key[j]:
            key.insert(j,a)
            value.insert(j,b)
            last = False
            break
    if last:
        key.append(a)
        value.append(b)
for i in range(n):
    s += value[i]
    if k <= s:
        print(key[i])
        break


### FIXED CODE ###

n,k = map(int,input().split())
arr = [0 for i in range(1,10**5+2)]
s = 0
for i in range(n):
    a,b = map(int, input().split())
    arr[a] += b
for i in range(1,10**5+1):
    s += arr[i]
    if k <= s:
        print(i)
        break
### BUGGY CODE ###

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

dp = [0]*(h+1)

for i in range(1,h+1):
    mn = 10**9
    for j in ab:
        hp = j[0]
        mp = j[1]  
        if i-hp<0:
            mn = min(mp,mn)
        else:
            mn = min(dp[i-hp]+mp, mn)
        dp[i] = mn

print(dp[h])


### FIXED CODE ###

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

dp = [0]*(h+1)

for i in range(1,h+1):
    mn = 10**9
    for j in ab:
        hp = j[0]
        mp = j[1]  
        if i-hp<0:
            mn = min(mp,mn)
        else:
            mn = min(dp[i-hp]+mp, mn)
        dp[i] = mn

print(dp[h])
### BUGGY CODE ###

import itertools
n,m,q=(int(i) for i in input().split())
l=[]
r=[i+1 for i in range(m)]
g=itertools.combinations_with_replacement(r,n)
point=0
def checker(x,l):
  p=0
  for i in range(len(l)):
    a,b,c,d=(l[i][j] for j in range(4))
    if x[b]-x[a]==c:
      p+=d
  return p
for i in range(q):
  a,b,c,d=(int(i) for i in input().split())
  a-=1
  b-=1
  l.append([a,b,c,d])
for i in g:
  p=checker(i,l)
  if p>point:
    point=p
print(point)


### FIXED CODE ###

import itertools
n,m,q=(int(i) for i in input().split())
l=[]
r=[i+1 for i in range(m)]
point=0
def checker(x,l):
  p=0
  for i in range(len(l)):
    if x[l[i][1]]-x[l[i][0]]==l[i][2]:
      p+=l[i][3]
  return p
for i in range(q):
  a,b,c,d=(int(i) for i in input().split())
  a-=1
  b-=1
  l.append([a,b,c,d])
for i in itertools.combinations_with_replacement(r,n):
  p=checker(i,l)
  if p>point:
    point=p
print(point)
### BUGGY CODE ###

from itertools import product

h, w, k = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]

ans = float("inf")
for pat in product([1, 0], repeat=h):
    prev = 2
    sm = -1
    for e in pat:
        if e != prev:
            sm += 1
        prev = e
    #print(pat)
    #print(sm)

    ss = [[0] * w for _ in range(h)]
    for wi in range(w):
        acc = 0
        prev = 2
        for hi, e in enumerate(pat):
            if e != prev:
                acc = 0
            if s[hi][wi]:
                acc += 1
            ss[hi][wi] = acc
            prev = e

    sss = [[0] * w for _ in range(h)]
    for hi in range(h):
        for wi in range(w):
            if wi == 0:
                sss[hi][wi] = ss[hi][wi]
            else:
                sss[hi][wi] = sss[hi][wi-1] + ss[hi][wi]

    base = [0] * h
    cp_prev = [0] * h
    for wi in range(w):
        mx = 0
        cp = [0] * h
        for hi in range(h):
            mx = max(mx, sss[hi][wi] - base[hi])
            cp[hi] = sss[hi][wi]
        if mx > k:
            if wi == 0:
                sm = 10000
            sm += 1
            base = cp_prev
        cp_prev = cp

    ans = min(ans, sm)

print(ans)


### FIXED CODE ###

from itertools import product

h, w, k = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]

ans = float("inf")
for pat in product([1, 0], repeat=h):
    prev = 2
    sm = -1
    for e in pat:
        if e != prev:
            sm += 1
        prev = e
    #print(pat)
    #print(sm)

    ss = [[0] * w for _ in range(h)]
    for wi in range(w):
        acc = 0
        prev = 2
        for hi, e in enumerate(pat):
            if e != prev:
                acc = 0
            if s[hi][wi]:
                acc += 1
            ss[hi][wi] = acc
            prev = e

    sss = [[0] * w for _ in range(h)]
    for hi in range(h):
        for wi in range(w):
            if wi == 0:
                sss[hi][wi] = ss[hi][wi]
            else:
                sss[hi][wi] = sss[hi][wi-1] + ss[hi][wi]

    base = [0] * h
    cp_prev = [0] * h
    for wi in range(w):
        mx = 0
        cp = [0] * h
        for hi in range(h):
            mx = max(mx, sss[hi][wi] - base[hi])
            cp[hi] = sss[hi][wi]
        if mx > k:
            if wi == 0:
                sm = 10000
            sm += 1
            base = cp_prev
        cp_prev = cp

    ans = min(ans, sm)

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

N = int(input())

ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))

# case
# すべて a > b
# すべて b < a
# 2個  a > b
# 1個  a > b

# weight:ga price:gb どんぐり weight:1 price:1


vmax = 0
for g in range(0,N + 1, ga):
    for s in range(0,N + 1 - g, sa):
        v = (g // ga) * gb + (s // sa) * sb
        amari = N - g - s
        if amari < 0:
            break
        if ba < bb:
            v += amari // ba * bb
            amari %= ba
        v += amari

        vmax = max(vmax, v)

D = vmax
vmax = D

if ba < bb:
    tmp = sa,sb
    sa,sb = ba,bb
    ba,bb = tmp

for g in range(0,D + 1, gb):
    if ga < gb and g > 0:
        break
    for s in range(0, D + 1 - g, sb):
        if sa < sb and s > 0:
            break
        v = (g // gb) * ga + (s // sb) * sa
        amari = D - g - s
        if amari < 0:
            break
        if ba > bb:
            v += amari // bb * ba
            amari %= bb
        v += amari

        vmax = max(vmax, v)

print(vmax)


### FIXED CODE ###

N = int(input())

ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))

# case
# すべて a > b
# すべて b < a
# 2個  a > b
# 1個  a > b

# weight:ga price:gb どんぐり weight:1 price:1


vmax = 0
for g in range(0,N + 1, ga):
    for s in range(0,N + 1 - g, sa):
        v = (g // ga) * gb + (s // sa) * sb
        amari = N - g - s
        if amari < 0:
            break
        if ba < bb:
            v += amari // ba * bb
            amari %= ba
        v += amari

        vmax = max(vmax, v)

D = vmax
vmax = D

if ba < bb:
    tmp = sa,sb
    sa,sb = ba,bb
    ba,bb = tmp

for g in range(0,D + 1, gb):
    if ga < gb and g > 0:
        break
    for s in range(0, D + 1 - g, sb):
        if sa < sb and s > 0:
            break
        v = (g // gb) * ga + (s // sb) * sa
        amari = D - g - s
        if amari < 0:
            break
        if ba > bb:
            v += amari // bb * ba
            amari %= bb
        v += amari

        vmax = max(vmax, v)

print(vmax)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6+10)
def gethelp(mask1,mask2,ind):
    # print(mask1,mask2)
    global n,a,dp
   
    if dp.get(str(mask1)+' '+str(mask2),None)!=None:
        return dp[str(mask1)+' '+str(mask2)]
    dp[str(mask1)+' '+str(mask2)]=0
    for i in range(ind+1,n):
        if (mask1&(1<<i))==1:
            continue
        for j in range(n):
            if (mask2&(1<<j))==1:
                continue
            if a[i][j]==1:
                # andand (mask2&(1<<j))==0:
                # print('here ',end=' ')
                # print(i,j)
                dp[str(mask1)+' '+str(mask2)]+=gethelp(mask1|(1<<i),mask2|(1<<j),i)
    
    return dp[str(mask1)+' '+str(mask2)]
n=int(input())
a=[list() for i in range(n)]
for _ in range(n):
    a[_]=list(map(int,input().split()))
dp=dict()
dp[str((1<<n)-1)+' '+str((1<<n)-1)]=1 
# print(dp)
t=gethelp(0,0,-1)
# print(dp)/
print(t)

### FIXED CODE ###

n = int(input())
a = [[int(x) for x in input().split()] for i in range(n)]
dp = [-1 for i in range(1 << n)]
dp[0] = 1
mod=10**9+7
def gethelp(bit, i):
    if dp[bit] != -1:
        return dp[bit]
    else:
        tmp = 0
        for j in range(n):
            if bit & (1 << j) and a[i][j]:
                tmp += gethelp(bit ^ (1 << j), i+1)
    dp[bit] = tmp % mod
    return dp[bit]
print(gethelp(2**n-1, 0))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
d = {}

for i in range(n):
    if a[i] in d:
        d[a[i]] += 1
    else:
        d[a[i]] = 1


d_c = {}
d_2_c = {}
for i in d:
    d_c[i] = d[i] * (d[i] - 1) // 2
    d_2_c[i] = (d[i] - 1) * (d[i] - 2) // 2


d_3 ={}

for i in range(n):
    b = a[i]
    count = 0
    if b not in d_3:
        for j in d:
            if j != b:
                count += d_c[j]
            else:
                count += d_2_c[j]
        d_3[b] = count
        print(count)
    else:
        print(d_3[b])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
d = {}

for i in range(n):
    if a[i] in d:
        d[a[i]] += 1
    else:
        d[a[i]] = 1

count = 0
for i in d:
    count += d[i] * (d[i] - 1) // 2


for i in range(n):
    b = d[a[i]]
    print(count-b+1)
### BUGGY CODE ###

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

ans=0
for i in range(N):
    if A[i]>N-2: continue
    for j in range(i+A[i]+1,N):
        s=A[i]+A[j]
        if s==j-i:
            ans+=1
print(ans)

### FIXED CODE ###

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

Aii=[0]*(N)
Ajj=[0]*(N)

for i in range(N):
    x=A[i]+i+1
    y=i+1-A[i]
    if 1<x<N: Aii[x]+=1
    if 1<y<N: Ajj[y]+=1

ans=0
for i in range(N):
    ans+=Aii[i]*Ajj[i]

print(ans)