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

import numpy as np


def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_list = amari(n)
    l = len(amari_list)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            shift_list = np.array([shift(j * amari_list[i % l] % n, ans_list)
                                   for j in range(10)], dtype='int64')

            ans_list = np.mod(np.sum(shift_list, axis=0), mod)

        else:
            t = int(s) * amari_list[i % l] % n
            ans_list = shift(t, ans_list)

    print(ans_list[r] % mod)


def shift(r, num_list):
    l = len(num_list)
    return np.array([num_list[(i + l - r) % l] for i in range(l)], dtype='int64')


def initial(s, n):
    if s == "?":
        return np.array([1 if i < 10 else 0 for i in range(n)], dtype='int64')
    else:
        return np.array([1 if i == int(s) else 0 for i in range(n)], dtype='int64')


def amari(n):
    ret = []
    for i in range(n+1):
        r = (10**i) % n
        if r in ret:
            return ret
        else:
            ret.append(r)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np


def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_l = amari_list(n)
    amari_m = amari_matrix(n, amari_l)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            ans_list = np.dot(ans_list, amari_m[i % len(amari_m)]) % mod
        else:
            t = int(s) * amari_l[i % len(amari_l)] % n
            ans_list = np.roll(ans_list, t)

    print(int(ans_list[r] % mod))


def initial(s, n):
    if s == "?":
        return np.array([1 if i < 10 else 0 for i in range(n)], dtype='int64')
    else:
        return np.array([1 if i == int(s) else 0 for i in range(n)], dtype='int64')


def shift(n, r):
    return np.array([[1 if (i - j + r) % n == 0 else 0 for j in range(n)] for i in range(n)])


def amari_list(n):
    ret = []
    for i in range(n + 1):
        r = 10**i % n
        if r in ret:
            return ret
        else:
            ret.append(r)


def amari_matrix(n, amari_list):
    ret = np.zeros((len(amari_list), n, n))
    for i, j in enumerate(amari_list):
        tmp = np.zeros((n, n))
        for k in range(10):
            tmp += shift(n, j * k % n)
        ret[i] = tmp
    return ret


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

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

ans=0
def cheap(x,y):
    x=int(x/(2**y))
    return x

i=0
while(i<M):
    A.sort(reverse=True)
    A[0]=cheap(A[0],1)
    i+=1

for i in range(0,N):
    ans+=A[i]

print(ans)



### FIXED CODE ###

import heapq

N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range (0,len(A)):
    A[i]*=-1

heapq.heapify(A)

ans=0
def cheap(x,y):
    x=int(x/(2**y))
    return x

i=0
while(i<M):
    tmp=heapq.heappop(A)
    tmp=cheap(tmp,1)
    heapq.heappush(A,tmp)
    i+=1

for i in range(0,N):
    ans+=A[i]

print(ans*(-1))
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
import time

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
P = [0] * N
cnt = 0
ALL = N*(N-1)//2
s = time.time()
for day in range(ALL):
    if time.time()-s > 1.9:
        print(N*(N-1)//2)
        break
    used = [0] * N
    flag = 0
    for i, p in enumerate(P):
        if p != N-1 and used[i] == 0:
            x = A[i][p]
            if x < N and used[x] == 0 and A[x][P[x]] == i:
                P[i] += 1
                P[x] += 1
                used[i] = 1
                used[x] = 1
                flag = 1
                cnt += 1
    if cnt == ALL:
        print(day+1)
        break
    if flag == 0:
        print(-1)
        break


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
import time

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
P = [0] * N
cnt = 0
ALL = N*(N-1)//2
s = time.time()
for day in range(ALL):
    if time.time()-s > 1.6:
        print(N*(N-1)//2)
        break
    used = [0] * N
    flag = 0
    for i, p in enumerate(P):
        if p != N-1 and used[i] == 0:
            x = A[i][p]
            if x < N and used[x] == 0 and A[x][P[x]] == i:
                P[i] += 1
                P[x] += 1
                used[i] = 1
                used[x] = 1
                flag = 1
                cnt += 1
    if cnt == ALL:
        print(day+1)
        break
    if flag == 0:
        print(-1)
        break
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
lst = [a+b for a in A for b in B]
lst.sort(reverse=True)
lst = [e+c for e in lst[:k] for c in C]
lst.sort(reverse=True)
for i in range(k): print(lst[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
lst = [a+b for a in A for b in B]
lst.sort(reverse=True)
lst = [e+c for e in lst[:k] for c in C]
lst.sort(reverse=True)
for i in range(k): print(lst[i])
### BUGGY CODE ###

def resolve():
    A, B, K = list(map(int, input().split()))
    l = [i for i in range(A, B+1)]
    if len(l) >= 2 * K:
        ls = l[:K] + l[-K:]
    else:
        ls = l

    print('\n'.join(map(str, ls)))
    return

resolve()

### FIXED CODE ###

def resolve():
    A, B, K = list(map(int, input().split()))
    if B - A + 1 >= 2 * K:
        ls = [i for i in range(A, A+K)] + [i for i in range(B-K+1, B+1)]
    else:
        ls = [i for i in range(A, B+1)]

    print('\n'.join(map(str, ls)))
    return

resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
ans=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        ans[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
for i in range(h*w-1,d-1,-1):
    ans[i]=abs(ans[i][0]-ans[i-d][0])+abs(ans[i][1]-ans[i-d][1])
for i in range(d):
    ans[i]=0
for i in range(q):
    print(sum(ans[i] for i in range(l[i]+d-1,r[i],d)))

### FIXED CODE ###

import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
ans=[0]*(h*w)
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(A[i][0]-A[i-d][0])+abs(A[i][1]-A[i-d][1])
for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append([v-1,a,b])
    g[v-1].append([u-1,a,b])
  import heapq,math
  dp=[[math.inf]*(100*51)for _ in range(n)]
  kakutei=[[0]*(100*51)for _ in range(n)]
  dp[0][min(s,100*51-1)]=0
  todo=[[0,0,min(s,100*51-1)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[math.inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(100*51-1,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()
### BUGGY CODE ###

s = input()
n = int(input())
c = 0
left_l = ['', '']
right_l = ['', '']
s_l = [s, s[::-1]]
for _ in range(n):
  lst = [i for i in input().split()]
  if lst[0] == '1':
    if c == 1:
      s_l[0], s_l[1] = s_l[1], s_l[0]
      #print(s)
    else:
      s_l = [right_l[1] + s_l[1] + left_l[1], left_l[0] + s_l[0] + right_l[0]]
      left_l[0], left_l[1] = '', ''
      right_l[0], right_l[1] = '', ''
      c = 1
      #print(s)
  elif lst[0] == '2':
    c = 0
    if lst[1] == '1':
      left_l[0] = lst[2] + left_l[0]
      left_l[1] = left_l[1] + lst[2]
    elif lst[1] == '2':
      right_l[0] = right_l[0] + lst[2]
      right_l[1] = lst[2] + right_l[1]
s = left_l[0] + s_l[0] + right_l[0]
print(s)

### FIXED CODE ###

s = input()
n = int(input())
c = 0
left_l = ['', '']
right_l = ['', '']
s_l = [s, s[::-1]]
for _ in range(n):
  lst = [i for i in input().split()]
  if lst[0] == '1':
    if c == 1:
      s_l[0], s_l[1] = s_l[1], s_l[0]
      #print(s)
    else:
      s_l = [right_l[1] + s_l[1] + left_l[1], left_l[0] + s_l[0] + right_l[0]]
      left_l[0], left_l[1] = '', ''
      right_l[0], right_l[1] = '', ''
      c = 1
      #print(s)
  elif lst[0] == '2':
    c = 0
    if lst[1] == '1':
      left_l[0] = lst[2] + left_l[0]
      left_l[1] = left_l[1] + lst[2]
    elif lst[1] == '2':
      right_l[0] = right_l[0] + lst[2]
      right_l[1] = lst[2] + right_l[1]
w = left_l[0] + s_l[0] + right_l[0]
print(w)
### BUGGY CODE ###

N=int(input())
S=input()
count=0
for i in range(0,N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if S[i]==S[j]:
                break
            if S[j]!=S[k] and S[k]!=S[i] and j-i!=k-j:
                count+=1
print(count)

### FIXED CODE ###

N=int(input())
S=input()
R=S.count("R")
G=S.count("G")
B=S.count("B")


count=R*G*B
for i in range(0,N-2):
    for j in range(i+1,N-1):
        k=j+(j-i)
        if k>=N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            count=count-1

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

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

#https://atcoder.jp/contests/abc082/tasks/abc082_c
length = int(input())
a = [int(i) for i in input().split()]

count = 0
for i in range(length):
	if(i+1 <= a.count(i+1)):
		count += i+1
print(length - count)

### FIXED CODE ###

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

#https://atcoder.jp/contests/abc082/tasks/abc082_c
length = int(input())
a = [int(i) for i in input().split()]
set_a = set(a)

count = 0
for i in set(a):
	if (i > length):
		continue
	if(i <= a.count(i)):
		count += i
print(length - count)
### BUGGY CODE ###

import math
import sys
readline = sys.stdin.readline


def main():
    n, k = map(int, readline().rstrip().split())
    a = list(map(int, readline().rstrip().split()))
    setA = list(set(a))
    arr = []
    for l in setA:
        arr.append(a.count(l))
    print(sum(sorted(arr, reverse=True)[k: len(arr)]))


if __name__ == '__main__':
    main()

    

### FIXED CODE ###

import math
import sys
from collections import Counter
readline = sys.stdin.readline


def main():
    n, k = map(int, readline().rstrip().split())
    a = list(map(int, readline().rstrip().split()))
    c = Counter(a)
    print(sum(sorted(c.values(), reverse=True)[k: len(c)]))


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

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

cnt = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                cnt = cnt + 1

print(cnt)

### FIXED CODE ###

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

cnt = 0

for x in range(k+1):
    for y in range(k+1):
        z = s - (x + y)
        if z >= 0 and z <= k:
            cnt = cnt + 1
#        for z in range(k+1):
#            if x + y + z == s:
#                cnt = cnt + 1

print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
#dp[v]: start from v maxpath
dp = [-1 for _ in range(N)]

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

#solve DAG and topological sort by recursive funciton
def f(v,G=gragh):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for u in G[v]:
        ret = max(ret, f(u) + 1)
    return ret
for v in range(N):
    dp[v] = f(v)
print(max(dp))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
#dp[v]: start from v maxpath
dp = [-1 for _ in range(N)]

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

#solve DAG and topological sort by memo recursive funciton
def f(v,G=gragh):
    if dp[v] != -1:
        return dp[v]
    ret = 0
    for u in G[v]:
        ret = max(ret, f(u) + 1)
    dp[v] = ret
    return ret
for v in range(N):
    dp[v] = f(v)
print(max(dp))
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
INF = 10**4+1
dp = [INF]*n
dp[0]=0
for i in range(1,n):
  dp[i] = min([dp[j] + abs(h[j]-h[i]) for j in range(max(0, i-k),i)])
print(dp[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
INF = 10**4+1
dp = [INF]*n
dp[0]=0
for i in range(1,n):
  dp[i] = min([dp[j] + abs(h[j]-h[i]) for j in range(max(0, i-k),i)])
print(dp[n-1])
### BUGGY CODE ###

import numpy as np

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum = np.zeros(10**4+1)
bsum[0] = 0
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        min_bsum = min(min_bsum,bsum[max(0,i-a[atk])]+b[atk])
    bsum[i] = min_bsum

#指定のHのコストを表示
print(int(bsum[h]))


### FIXED CODE ###

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

n = int(input())
a = list(map(int,input().split()))
max = 0
for i in range(n):
    li = a[:i] + a[i + 1:]
    tmp = gcd_list(li)
    if tmp > max:
        max = tmp
print(max)

### FIXED CODE ###

import fractions
from functools import reduce

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

#累積GCD
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    #left.append(math.gcd(left[i],a[i]))
    left[i + 1] = (fractions.gcd(left[i],a[i]))
    #right.insert(0,math.gcd(right[0],a[n - 1 - i]))
    right[n - i - 1] = (fractions.gcd(right[n - i],a[n - 1 - i]))
#print(left)
#print(right)

ans = 0
for i in range(n):
    ans = max(ans,fractions.gcd(left[i],right[i + 1]))
print(ans)
### BUGGY CODE ###

N,M = map(int, input().split())
A = list(map(int, input().split()))
 
def second_large(x):
    y = x.copy()
    y.remove(max(y))
    return max(y)
 
if N>=2:
  while M>=1:
    fm_n = max(A)
    sm_n = second_large(A)
    div_m = fm_n/sm_n
    i=1
    while 2**(i+1)<=div_m:
      i+=1
 
    if M>=i:
      A[A.index(max(A))]=fm_n//(2**i)
      M -= i
    else:
      A[A.index(max(A))]=fm_n//(2**M)
      M = 0
 
  print(sum(A))
else:
    i=1
    while 2**(i+1)<=A[0]:
      i+=1
    if M>=i:
      print(0)
    else:
      print(A[0]//2**M)

### FIXED CODE ###

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

l = len(A)

if N>=2:
  while M>=1:
    A.sort(reverse=True)
    div = A[0]//2
    
    for i in range(l):
      if A[i]>=div:
        if M>=1:
          A[i] = A[i]//2
          M -= 1
        else:
          break
      else:
        break
 
  print(sum(A))
else:
    i=1
    while 2**(i+1)<=A[0]:
      i+=1
    if M>=i:
      print(0)
    else:
      print(A[0]//2**M)
### BUGGY CODE ###

N = int(input())
A = [0] * N
m = 0
for i in range(N):
    A[i] = int(input())
    if A[i] > m:
        m = A[i]
for i in range(N):
    if A[i] != m:
        print(m)
    else:
        A[i] = 0
        print(max(A))
        A[i] = m

### FIXED CODE ###

N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input())
tmp = sorted(A)
m1 = tmp[-1]
m2 = tmp[-2]
for i in range(N):
    if A[i] != m1:
        print(m1)
    else:
        print(m2)
### BUGGY CODE ###

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

hit = [False] * N

for i in range(0, N):
    if S[i:i+2] == 'AC':
        hit[i] = True

for _ in range(0, Q):
    l, r = map(int, input().split())
    print(sum(x for x in hit[l-1:r-1]))


### FIXED CODE ###

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

hit = [0] * N

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

    if S[i:i+2] == 'AC':
        hit[i + 1] += 1

for _ in range(0, Q):
    l, r = map(int, input().split())
    result = hit[r - 1] - hit[l - 1]
    print(result)
### BUGGY CODE ###

N = int(input())
hlist = list(map(int, input().split()))
cost = [-1 for _ in range(N)]
cost[0] = 0
cost[1] = abs(hlist[1] - hlist[0])
#再帰
"""
def function(n)
if 終了条件 return 初項
return function(n-1)を処理したもの
"""
def dp(n):
  #print(n)
  if n==0: return cost[0]
  elif n==1: return cost[1]
  else: return min(dp(n-1)+abs(hlist[n]-hlist[n-1]), dp(n-2)+abs(hlist[n]-hlist[n-2]))

for i in range(N):
  cost[i] = dp(i)
print(cost[-1])

### FIXED CODE ###

N = int(input())
hlist = list(map(int, input().split()))
cost = [-1 for _ in range(N)]

def dp(n):
  if n==0: return 0
  if n==1: return abs(hlist[1] - hlist[0])
  else: return min(cost[n-1]+abs(hlist[n]-hlist[n-1]), cost[n-2]+abs(hlist[n]-hlist[n-2]))

for i in range(N):
  cost[i]=dp(i)
print(cost[-1])
### 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


N, K = map(int, input().split())
ac = [0] * (N + 1)
eps = 10 ** -6
place = {0: 0}
for i in range(N):
    a = int(input()) - K
    ac[i+1] = ac[i] + a + eps
    place[ac[i+1]] = i+1
ac.sort()
ac_cmpr = [0] * (N+1)
for i in range(N+1):
    ac_cmpr[place[ac[i]]] = i + 1
bit = Bit(N+2)
bit.add(ac_cmpr[0], 1)
ans = 0
for i in range(1, N+1):
    ans += bit.sum(ac_cmpr[i])
    bit.add(ac_cmpr[i], 1)

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


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


def main():
    N, K = map(int, input().split())
    ac = [0] * (N + 1)
    place = {0: 0}
    for i in range(N):
        a = int(input()) - K
        ac[i+1] = ac[i] + a * (10 ** 5) + 1
        place[ac[i+1]] = i+1
    ac.sort()
    ac_cmpr = [0] * (N+1)
    for i in range(N+1):
        ac_cmpr[place[ac[i]]] = i + 1
    bit = Bit(N+2)
    bit.add(ac_cmpr[0], 1)
    ans = 0
    for i in range(1, N+1):
        ans += bit.sum(ac_cmpr[i])
        bit.add(ac_cmpr[i], 1)

    print(ans)


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

n = int(input())
bits = set()
count = 0
ans = []
for i in range(n):
    x = int(input())
    if x in bits:
        y = x
        while y in bits:
            y -= 1
        if y == 0 and count != x:
            ans.append("No")
        else:
            bits.add(y)
            if y == 0:
                ans.append("Yes")
                if i <= n-2:
                    ans.append("No\n"*(n-2-i) + "No")
                break
            count += 1
            for i in range(y+1, x+1):
                bits.remove(i)
                count -= 1
            ans.append("Yes")
    else:
        bits.add(x)
        count += 1
        ans.append("Yes")
print("\n".join(ans))

### FIXED CODE ###

n = int(input())
bits = set()
c1 = 0
count = 0
ans = []
for i in range(n):
    x = int(input())
    if x in bits:
        y = x
        while c1 < y and y in bits:
            y -= 1
        if y <= c1:
            y = 0
        if y == 0 and count != x:
            c1 = max(x, c1)
            ans.append("No")
        else:
            bits.add(y)
            ans.append("Yes")
            count += 1
            if y == 0:
                if i <= n-2:
                    ans.append("No\n"*(n-2-i) + "No")
                break
            for i in range(y+1, x+1):
                bits.remove(i)
                count -= 1
    else:
        bits.add(x)
        count += 1
        ans.append("Yes")
print("\n".join(ans))
### BUGGY CODE ###

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

if n == 0:
    if As[0] == 1: print(1)
    else: print(-1)
    exit()
    
# 下から見る
As_r = As[::-1]
p = As_r[0]
# とりうる最大値
a_pre = p
qs = [p]
# とりうる最小値
mn = As_r[0]

# 深さ n-1から0まで
for i,a in enumerate(As_r[1:]):
    d = n - i - 1
    p = min(2**d, p + a)
    mn = (mn+1)//2 + a
    a_pre = a
    qs.append(p)

if mn != 1:
    print(-1)
    exit()

qs.reverse()
# print(qs,As)
ans = qs[0]
cnt = qs[0]
# 上から見る
for i in range(1,n+1):
    qs[i] = min(2**i, 2*(qs[i-1]-As[i-1]),qs[i])
print(sum(qs))

### FIXED CODE ###

from itertools import accumulate
n = int(input())
As = list(map(int, input().split()))

if n == 0:
    if As[0] == 1:print(1)
    else:print(-1)
    exit()


if As[0] != 0:
    print(-1)
    exit()

b = 1
ans = 1
acc = list(accumulate(As))
s = acc[-1]
for ac,a in zip(acc[1:], As[1:]):
    # print(s-ac,2*b-a)
    b = min(2*b-a, s-ac)
    if b < 0:
        print(-1)
        exit()
    ans += b+a
print(ans)