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

import sys
input = sys.stdin.buffer.readline

import bisect

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

for i in range(M):
    B, C = map(int,input().split())
    index = bisect.bisect_left(A,C)
    if B < index :
        A = [C] * (B) + A[B:]
    else:
        A = [C] * (index) + A[index:]
    A.sort()
print(sum(A))

### FIXED CODE ###

import bisect
import itertools

N, M  = map(int,input().split())
A = sorted(list(map(int,input().split())))
D = []

for i in range(M):
    B, C = map(int,input().split())
    D.append((B,C))

D.sort(key = lambda x:x[1],reverse = True)

cnt = 0
ans = []
for b, c in D:
    for i in range(b):
        ans.append(c)
    cnt += b
    if cnt >=N:
        break
#print(D)
#print(ans)
res = sum(A)
for i in range(min(N,len(ans))):
    if ans[i]-A[i]>0:
        res += ans[i] - A[i]
    else:
        break
print(res)
### BUGGY CODE ###

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=lambda x:x[1])
for i in range(N):
    xy[i][1] = i+1
xy.sort()
for i in range(N):
    xy[i][0] = i

# x<xi,y<yi
l1 = [0]*N
# x<xi,y>yi
l2 = [0]*N
# x>xi,y<yi
r1 = [0]*N
# x>xi,y>yi
r2 = [0]*N

bit = BIT(N)
for i in range(N):
    l1[i] = bit.sum(xy[i][1])
    l2[i] = i-l1[i]
    r1[i] = xy[i][1]-l1[i]-1
    r2[i] = N-xy[i][1]-l2[i]
    bit.add(xy[i][1],1)

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod
for i in range(N):
    ans += (pow2[l2[i]]-1)*(pow2[r1[i]]-1)*pow2[r2[i]]*pow2[l1[i]]
    ans += (pow2[r2[i]]-1)*(pow2[l1[i]]-1)*(pow2[l2[i]]+pow2[r1[i]]-1)
    ans %= mod
print(ans)

### FIXED CODE ###

from operator import itemgetter

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=itemgetter(1))
for i in range(N):
    xy[i][1] = i+1
xy.sort(key=itemgetter(0))

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod

bit = BIT(N)
for i in range(N):
    l1 = bit.sum(xy[i][1])
    l2 = i-l1
    r1 = xy[i][1]-l1-1
    r2 = N-xy[i][1]-l2
    bit.add(xy[i][1],1)
    ans += (pow2[l2]-1)*(pow2[r1]-1)*pow2[r2]*pow2[l1]
    ans += (pow2[r2]-1)*(pow2[l1]-1)*(pow2[l2]+pow2[r1]-1)
    ans %= mod

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

N, A, B = map(int, input().split())
count = 0

while N > 0:
  if N >= A + B:
    count += A
  else:
    count += min(A, N)
  N -= A + B

print(count)

### FIXED CODE ###

N, A, B = map(int, input().split())
n, r = divmod(N, A+B)

ans = A * n  + min(A, r)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)

s = input()
n = 13

mod=10**9+7

dp=[0] * n
dp[0] =1

mul=1

for i in range(len(s)-1,-1,-1):

    nextDP = [0] * n

    c=s[i]

    if c =='?':
        for k in range(10):
            for j in range(n):
                nextDP[(k*mul+j)%n] += dp[j]

    else:
        k=int(s[i])
        for j in range(n):
            nextDP[(k*mul+j)%n] += dp[j]

    mul*=10
    dp=nextDP

print(dp[5]%mod%mod)

### FIXED CODE ###

s=list(input())
mod=10**9+7
n=len(s)

dp=[[0]*13 for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    if s[i]=="?":
        for k in range(10):
            for j in range(13):
                p=(k+10*j)%13
                dp[i+1][p]+=dp[i][j]
                dp[i+1][p]%=mod

    else:

        for j in range(13):
            p=(int(s[i])+10*j)%13
            dp[i+1][p]+=dp[i][j]
            dp[i+1][p]%=mod


print(dp[n][5])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(s: str, t: str):
    len_s = len(s)
    len_t = len(t)

    dp = [[""] * (len_t+1) for _ in range(len_s+1)]

    for i in range(len_s):
        for j in range(len_t):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + s[i]
            else:
                if len(dp[i+1][j]) > len(dp[i][j+1]):
                    dp[i+1][j+1] = dp[i+1][j]
                else:
                    dp[i+1][j+1] = dp[i][j+1]

    print(dp[-1][-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()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(s: str, t: str):
    n, m = len(s), len(t)
    dp = [[0]*(m+1) for _ in range(n+1)]

    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], dp[i][j] + 1)
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

    ans = ""
    while m > 0 and n > 0:
        if s[n-1] == t[m-1]:
            ans = s[n-1] + ans
            n -= 1
            m -= 1
        elif dp[n][m] == dp[n-1][m]:
            n -= 1
        else:
            m -= 1
    print(ans)


# 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()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


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

import math

def nyu():
    N,K= map(int,(input().split()))
    return K,N


def check(K,N ):
    min = 0
    abs_num = 0

    OLD_ABS =N
    NEW_ABS = abs(K-N)

    while NEW_ABS < OLD_ABS:
        OLD_ABS = N #OK
        N = NEW_ABS ##OK
        NEW_ABS =abs(K-N)
    #    print("N_NEW",NEW_ABS,"OLS_ABS",OLD_ABS,"N",N)
    print(N)

    

     
            
K,N = nyu()
check(K,N)
#print(S)



### FIXED CODE ###

import math

def nyu():
    N,K= map(int,(input().split()))
    return K,N


def check(K,N ):
    min = 0
    abs_num = 0

    N = N%K

    OLD_ABS =N
    NEW_ABS = abs(K-N)

    while NEW_ABS < OLD_ABS:
        OLD_ABS = N #OK
        N = NEW_ABS ##OK
        NEW_ABS =abs(K-N)
    #    print("N_NEW",NEW_ABS,"OLS_ABS",OLD_ABS,"N",N)
    print(N)     
            
K,N = nyu()
check(K,N)
#print(S)
### BUGGY CODE ###

n=int(input())
v=input().split()
o=[("0",0)]
e=[("0",0)]
for i in range(n//2):
    I=2*i
    O=len(o)
    E=len(e)
    for j in range(O):
        if v[I]==o[j][0]:
            o[j]=(o[j][0],o[j][1]+1)
            break
        elif j==O-1:
            o.append((v[I],1))
    for k in range(E):
        if v[I+1]==e[k][0]:
            e[k]=(e[k][0],e[k][1]+1)
            break
        elif k==E-1:
            e.append((v[I+1],1))
o.sort(key=lambda x:x[1])
e.sort(key=lambda x:x[1])
if o[-1][0]==e[-1][0]:
    if o[-1][1]<e[-1][1]:
        m=e[-1][1]+o[-2][1]
    else:
        m=o[-1][1]+e[-2][1]
else:
    m=o[-1][1]+e[-1][1]
print(n-m)


### FIXED CODE ###

N=int(input())
V=list(map(int,input().split()))
o={0:0}
e={0:0}
n=1
for i,v in enumerate(V):
    if n:
        if v in o.keys():
            o[v]+=1
        else:
            o[v]=1
    else:
        if v in e.keys():
            e[v]+=1
        else:
            e[v]=1
    n=1-n
O=sorted(o.items(),key=lambda x:-x[1])
E=sorted(e.items(),key=lambda x:-x[1])
if O[0][0]==E[0][0]:
    m=max(O[0][1]+E[1][1],E[0][1]+O[1][1])
else:
    m=O[0][1]+E[0][1]
print(N-m)
### BUGGY CODE ###

from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n, k = map(int, input().split())
p_array = np.array(list(map(int, input().split())))

def expc(x):
    return (x + 1.0)/2.0

sum_max = sum(expc(p_array[0:k]) )
temp_sum = sum_max
for i in range(n-k):
    temp_sum -= expc(p_array[i])
    temp_sum += expc(p_array[i+k])
    if temp_sum > sum_max:
        sum_max = temp_sum

print(sum_max)



### FIXED CODE ###

from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n, k = map(int, input().split())
p_array = np.array(list(map(int, input().split())))
expc = lambda x: (x+1.0)/2.0
p_array = expc(p_array)

p_cum = np.cumsum(p_array)
p_cum_diff = p_cum[k:] - p_cum[0:n-k]
if len(p_cum_diff) > 0:
    print(max(p_cum_diff))
else:
    print(p_cum[-1])
### BUGGY CODE ###

n, l = map(int, input().split())
ss = [input() for _ in range(n)]
prefix = set()
out = dict()
for s in ss:
	u = ""
	for i in range(len(s)):
		u += s[i]
		prefix.add(u)
		out[u] = 1
grundy = 0
for p in list(prefix):
	le = len(p)
	if p[le-1] == "0":
		t = p[:le-1] + "1"
	else:
		t = p[:le-1] + "0"
	if t not in out:
		grundy ^= (l-le+1) & (-l+le-1)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

### FIXED CODE ###

import sys
#from collections import defaultdict
sys.setrecursionlimit(10**6)

def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [list(input())[::-1] for _ in range(n)]

def addTree(tree, sentence):
	if not sentence:
		return None   

	if sentence[-1] not in tree:
		tree[sentence[-1]] = {}

	p = sentence.pop()
	tree[p] = addTree(tree[p], sentence)

	return tree

def createTree(sentences):    
	tree = {}
	for sentence in sentences:
		tree = addTree(tree, sentence)

	return tree

tree = createTree(ss)
#print(tree)

grundy = 0
def dfs(cur, level):
	global grundy
	if cur is None:
		return
	elif len(cur) == 1:
		grundy ^= (l-level) & (-l+level)
	for k in cur.keys():
		dfs(cur[k], level+1)
	return
	
dfs(tree, 0)

if grundy == 0:
	print("Bob")
else:
	print("Alice")
### BUGGY CODE ###

from bisect import bisect_right
n, m = map(int, input().split())
cards = [int(i) for i in input().split()]
cards.sort()
manu = []
for i in range(m):
    b, c = map(int, input().split())
    manu.append((b, c))

manu.sort(reverse=True, key=lambda x: x[1]) # 変更すると大きいモノから行う。
p = 0
for b, c in manu:
    for i in range(b):
        if p + i < n and cards[p + i] < c:
            cards[p + i] = c
    p += b
ans = sum(cards)
print(ans)

### FIXED CODE ###

from bisect import bisect_right, bisect_left
n, m = map(int, input().split())
cards = [int(i) for i in input().split()]
cards.sort()
manu = []
for i in range(m):
    b, c = map(int, input().split())
    manu.append((b, c))

manu.sort(reverse=True, key=lambda x: x[1]) # 変更すると大きいモノから行う。
p = 0
for b, c in manu:
    if p < n and cards[p] < c:
        for i in range(b):
            if p + i < n and cards[p + i] < c:
                cards[p + i] = c
        p += b
    else:
        break
ans = sum(cards)
print(ans)
### BUGGY CODE ###

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

need =[2,5,5,4,5,6,3,7,6] 

dp = [[0 for i in range(N+1)] for j in range(M)]
dpmax = [0 for i in range(N+1)]

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    if j == need[A[i]-1]:
      dp[i][j] = A[i]
    elif j > need[A[i]-1]:
      if dpmax[j-need[A[i]-1]] != 0:
        dp[i][j] = max(int(str(A[i]) + str(dpmax[j-need[A[i]-1]])),
                       int(str(dpmax[j-need[A[i]-1]]) + str(A[i])))
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])

### FIXED CODE ###

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

if N % 2 == 0:
  if 1 in A:
    print(int('1'*(N//2)))
    exit()

need =(2,5,5,4,5,6,3,7,6)

if 2 in A and 3 in A:
  del A[A.index(2)]
if 3 in A and 5 in A:
  del A[A.index(3)]
if 6 in A and 9 in A:
  del A[A.index(6)]
if 1 in A and 4 in A:
  del A[A.index(4)]
if 6 in A and 7 in A:
  del A[A.index(6)] 
if 7 in A and 9 in A:
  del A[A.index(9)] 
if 1 in A and 6 in A:
  del A[A.index(6)] 
if 1 in A and 9 in A:
  del A[A.index(9)] 
  
A = tuple(A)
M = len(A)

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

def take_max():
  return max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      dp[i][j] = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        dp[i][j] = take_max()
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])
### BUGGY CODE ###

import sys

N, M = map(int, input().split())
p = list(map(int, input().split()))
pairs = [[int(c) for  c in l.strip().split()] for l in sys.stdin]

d1 = [set(pairs[0])]

for i in range(1,M):
  flag = -1
  for j in range(len(d1)):
    if len(d1[j] & set(pairs[i])) != 0:
      if flag != -1:
        d1[j] |= d1[flag]
        del d1[flag]
        break
      else:
        d1[j] |= set(pairs[i])
        flag = j
  if flag == -1:
    d1.append(set(pairs[i]))

ans = 0
for sub in d1:
  sub2 = {p.index(i)+1 for i in sub}
  ans += len(sub & sub2)

res = set(range(1,N+1))
for sub in d1:
  res -= sub

for c in res:
  if p[c-1] == c:
    ans += 1

print(ans)



### FIXED CODE ###

import sys

N, M = map(int, input().split())
p = list(map(int, input().split()))
p.insert(0,0)
pairs = [[int(c) for  c in l.strip().split()] for l in sys.stdin]

link = [[] for _ in  range(N+1)]
for i in range(M):
  x = pairs[i][0]
  y = pairs[i][1]
  link[x].append(y)
  link[y].append(x)


ans = 0
visited = set()
#数列の１つ１つの数字について
for i in range(1, N+1):

  #既に1度見た数字は飛ばす
  if i in visited:
    continue
  
  #linkedに交換可能なひとまとまりの数字をセットとして格納
  #ここでlinkedをリセット
  linked = set()

  #todoにはリンク先を調べないといけない数字のリストを格納
  todo = [i]
  while todo:

    #todoから1つずつ
    cur = todo.pop()
    for dest in link[cur]:

      #既にグループに入っている数字は飛ばす
      if dest not in linked:
        linked.add(dest)
        todo.append(dest)

  #「位置」を表すグループと「数字」を表すグループのオーバーラップ部分を数える
  ans += len(linked & set(p[n] for n in linked))
  #一度見た数字は再訪しない
  visited |= linked

#最後にまだ一度も見ていない数字のなかで、i = p[i]であるものを探す
for i in set(range(1,N+1)) - visited:
  ans += i == p[i]

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


def resolve():
  N = int(input())
  X = input()
  base_1_count = X.count("1")
  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)
  X_int_m = 1

  if base_1_count > 1:
    X_int_m = X_int%(base_1_count - 1)

# 低速バージョン
  for i in range(N):
    if X[i] == "1":
      Xi = X_int - 2**(N-i-1)
    else:
      Xi = X_int + 2**(N-i-1)
    count = 0
    while Xi != 0:
      # print(Xi)
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    # print("~~~~~~~~~~~~~~~")
    print(count)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
  N = int(input())
  X = input()

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = pow(2, N-i-1, base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + pow(2, N-i-1, base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

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

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

import sys
from collections import defaultdict

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

N = INT()
A = LIST()

# dp0[i][j] := i個目の要素まで見て、選んだ要素-選ばなかった要素=jで、直前を使っていない時の最大値
dp0 = [defaultdict(lambda: -INF) for i in range(N+1)]
# dp1[i][j] := i個目の要素まで見て、選んだ要素-選ばなかった要素=jで、直前を使った時の最大値
dp1 = [defaultdict(lambda: -INF) for i in range(N+1)]
dp0[0][0] = 0
for i, a in enumerate(A):
    for j in range(-2, 2):
        if j != -2:
            # 今回のaを使わない
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp0[i][j])
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp1[i][j])
        # 今回のaを使う
        dp1[i+1][j+1] = max(dp1[i+1][j+1], dp0[i][j] + a)
# 最終的に欲しい位置は偶奇で場合分け
if N % 2 == 0:
    # 偶数の時は使った数と使わなかった数が同じ
    ans = max(dp0[N][0], dp1[N][0])
else:
    # 奇数の時は使わなかった数が1つ多い
    ans = max(dp0[N][-1], dp1[N][-1])
print(ans)


### FIXED CODE ###

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

import sys
from collections import defaultdict

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

N = INT()
A = LIST()

# dp0[i][j] := i個目の要素まで見て、選んだ要素-選ばなかった要素=jで、直前を使っていない時の最大値
dp0 = [defaultdict(lambda: -INF) for i in range(N+1)]
# dp1[i][j] := i個目の要素まで見て、選んだ要素-選ばなかった要素=jで、直前を使った時の最大値
dp1 = [defaultdict(lambda: -INF) for i in range(N+1)]
dp0[0][0] = 0
for i, a in enumerate(A):
    for j in range(-2, 2):
        if j != -2:
            # 今回のaを使わない
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp0[i][j])
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp1[i][j])
        # 今回のaを使う
        dp1[i+1][j+1] = max(dp1[i+1][j+1], dp0[i][j] + a)
# 最終的に欲しい位置は偶奇で場合分け
if N % 2 == 0:
    # 偶数の時は使った数と使わなかった数が同じ
    ans = max(dp0[N][0], dp1[N][0])
else:
    # 奇数の時は使わなかった数が1つ多い
    ans = max(dp0[N][-1], dp1[N][-1])
print(ans)
### BUGGY CODE ###

a=[]
while 1:
    b=input()
    if b[2]=='d':break
    if b[0]=='i':a+=[int(b[7:])]
    else:c=max(a);print(c);a.remove(c)

### FIXED CODE ###

from heapq import *
a=[]
while 1:
    b=input()
    if b[2]=='d':break
    if b[0]=='i':heappush(a,-int(b[7:]))
    else:print(-heappop(a))
### BUGGY CODE ###

# coding: utf-8
N, K = list(map(int, input().split()))
mod = 10 ** 9 + 7
sum = 0
count = [0 for _ in range(K+1)]
pows = [0 for _ in range(K+1)]

def cal_pow(k, pows):
    if pows[k] == 0:
        pows[k] = pow(k,N)
        return pows[k]
    else:
        return pows[k]

for h in range(K):
    k = K-h
    sub, alpha = 0,2
    while True:
        if alpha*k <= K:
            sub += count[alpha*k]
            alpha += 1
        else:break
    count[k] = (cal_pow(K//k, pows) - sub) % mod

for k, c in enumerate(count):
    sum += k * c % mod
print(sum % mod)

### FIXED CODE ###

# coding: utf-8
N, K = list(map(int, input().split()))
mod = 10 ** 9 + 7
sum = 0
count = [0 for _ in range(K+1)]
pows = [0 for _ in range(K+1)]

def cal_pow(k, pows):
    if pows[k] == 0:
        pows[k] = pow(k,N, mod)
        return pows[k]
    else:
        return pows[k]

for h in range(K):
    k = K-h
    sub, alpha = 0,2
    while True:
        if alpha*k <= K:
            sub += count[alpha*k]
            alpha += 1
        else:break
    count[k] = (cal_pow(K//k, pows) - sub) % mod

for k, c in enumerate(count):
    sum += k * c % mod
print(sum % mod)
### BUGGY CODE ###

q = int(input())

lr = [list(map(int, input().split())) for _ in range(q)]

# 素数判定
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False

    return True

for i in range(q):
    cnt = 0
    for j in range(lr[i][0], lr[i][1]+1):
        if not is_prime(j):
            continue
        if is_prime((j+1)//2):
            cnt += 1
    print(cnt)

### FIXED CODE ###

q = int(input())

lr = [list(map(int, input().split())) for _ in range(q)]

def primes(n):
    # 1であれば素数であるリスト
    primes = [1] * (n+1)
    primes[0] = 0
    primes[1] = 0

    for i in range(2, int(n**0.5) + 1):
        if not primes[i]:
            continue
        for j in range(i * 2, n + 1, i):
            primes[j] = 0
    return primes

MAX = 100000
prime_list = primes(MAX)

# 2017に似た数値かどうかを求めるための累積和用のリスト作成
ans_list = [0] * (MAX + 1)
now = 0
for i in range(MAX):
    if prime_list[i] == 1 and prime_list[(i+1)//2] == 1:
        now += 1
    ans_list[i+1] = now

for i in range(q):
    print(ans_list[lr[i][1]+1] - ans_list[lr[i][0]])
### BUGGY CODE ###

import math
def c(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# xのn乗
def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

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

ans = pow_k(2,n) - c(n,a) - c(n,b) - 1

print(ans%(10**9+7))

### FIXED CODE ###

import math

# xのn乗
def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

# nCkの導出
def comb(n,k):
    nCk = 1
    # X
    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= mod

    # Y
    for i in range(1,k+1):
        nCk *= pow(i,mod-2,mod)
        nCk %= mod
    return nCk

n, a, b = map(int, input().split())
mod = 10**9+7

# ans = pow_k(2,n) - c(n,a) - c(n,b) - 1

ans = pow(2,n,mod) - 1 - comb(n,a) - comb(n,b)

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

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


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1=[0]*(2*(10**5)+10)
num2=[0]*(2*(10**5)+10)
for i in range(n):
    if a[i]+i+1<2*(10**5)+5:
        num1[a[i]+i+1]+=1
    if a[i]+1<i+1:
        num2[-a[i]+i+1]+=1
ans=0
for i in range(len(num1)):
    ans+=num1[i]*num2[i]
print(ans)