Harryxun/stf_run huggingface dataset:
def main():
    import sys 
    from fractions import gcd 
    input = sys.stdin.readline 

    def init(init_val):
        for i in range(n):
            seg[i+num-1] = init_val[i]
        for i in range(num-2,-1,-1):
            seg[i] = gcd(seg[2*i+1], seg[2*i+2])

    def update(k, x):
        k += num - 1
        seg[k] = x 
        while k:
            k = (k-1)//2
            seg[k] = gcd(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = gcd(res, seg[p])
            if q & 1 == 1:
                res = gcd(res, seg[q])
                q -= 1
            p //= 2
            q = (q - 1)//2

        if p==q:
            res = gcd(res, seg[p])
        else:
            res = gcd(gcd(res, seg[p]), seg[q])
        return res
         
    n= int(input())
    a = tuple(map(int, input().split())
    ide_ele = 0
    num = 2**(n-1).bit_length()
    seg = [ide_ele]*2*num
    init(a)    
                
    ans = -1
    for i in range(n):
        ans = max(ans, gcd(query(0,i), query(i+1,n)))
    print(ans) 

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys 
    from fractions import gcd 
    input = sys.stdin.readline 

    def init(init_val):
        for i in range(n):
            seg[i+num-1] = init_val[i]
        for i in range(num-2,-1,-1):
            seg[i] = gcd(seg[2*i+1], seg[2*i+2])

    def update(k, x):
        k += num - 1
        seg[k] = x 
        while k:
            k = (k-1)//2
            seg[k] = gcd(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return 0
        p += num - 1
        q += num - 2
        res = 0
        while q - p > 1:
            if p & 1 == 0:
                res = gcd(res, seg[p])
            if q & 1 == 1:
                res = gcd(res, seg[q])
                q -= 1
            p //= 2
            q = (q - 1)//2

        if p==q:
            res = gcd(res, seg[p])
        else:
            res = gcd(gcd(res, seg[p]), seg[q])
        return res
         
    n= int(input())
    a = tuple(map(int, input().split()))
    num = 2**(n-1).bit_length()
    seg = [0]*2*num
    init(a)    
                
    ans = -1
    for i in range(n):
        ans = max(ans, gcd(query(0,i), query(i+1,n)))
    print(ans) 

if __name__ == '__main__':
    main()
n=int(input())#入力

for a in range(10):
    for b in range(10):
        if a*b==n:
            print("Yes")
            break #Yesになった時にループを終了
    if a*b==81:
    print("No")#break(if文条件)が一度も起きなかった時のみ出力

### FIXED CODE ###

N=int(input())

list=[]
for i in range(1,10):
  for j in range(1,10):
    list.append(i*j)
if N in list:
  print("Yes")
else:
  print("No")
N,b,r = map(int, input().split())

num = int(N / (b+r))
rest = N - num * (b + r)
if rest >= b:
	print(num * b + b)
else:
	print(num * b + rest)

### FIXED CODE ###

S = input()

if S == "AAA" or S == "BBB":
  print("No")
else:
  print("Yes")
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    A=list(mi()) + [0]

    dp = [[0] * (2*10**5+10) for _ in range(N+1)]
    x = 1000//A[0]
    dp[0][x] = 1000 - x * A[0]


    for i in range(x):
        dp[0][i] = 1000 - i * A[0]

    mx = x
    for i in range(N):
        _mx = mx
        for m in range(mx+1):
            if not m < len(dp[i]): continue
            for n in [0,m]:
                dp[i+1][m-n] = max(0,dp[i+1][m-n],dp[i][m] + A[i+1] * n)
                # assert dp[i+1][m-n] >= 0
            
            if A[i+1] != 0:
                j = dp[i][m] // A[i+1]
                dp[i+1][m+j] = max(0,dp[i+1][m+j],dp[i][m] - A[i+1] * j)
                _mx = max(_mx,m+j)
                # assert dp[i+1][m+j] >= 0

        mx = _mx

    ans = 0
    for i in range(len(dp[N-1])):
        if dp[N-1][i] == 0: continue
        ans = max(ans, dp[N-1][i] + A[N-1] * i)

    # print(dp[3][10])
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    _A=list(mi())
    A = []

    for a in _A:
        if len(A) > 0 and A[-1] == a: continue
        A.append(a)
    
    N = len(A)
    bottoms = []
    
    if N < 2:
        print(1000)
        exit()

    if A[0] < A[1]:
        bottoms.append(0)

    for i in range(N-1):
        if not i+2 < len(A): continue
        # print(A[i], A[i+1], A[i+2])
        if A[i] > A[i+1] and A[i+1] < A[i+2]:
            bottoms.append(i+1)
    
    money = 1000
    kabu = 0
    # print(bottoms)
    for bi in bottoms:
        bottom = A[bi]
        i = bi
        while i < N-1 and A[i] < A[i+1]:
            i += 1
        
        top = A[i]

        # print(bi,i)
        # print(bottom,top)
        kabu += money//bottom
        money -= money//bottom * bottom
        
        money += kabu * top
        kabu = 0
        # print("money",money)
    
    print(money)

    

if __name__ == "__main__":
    main()
S = input()
T = input()
 
ans = 'UNRESTORABLE'
for i in range(len(S) - len(T) + 1):
    s = S[i:i+len(T)+1]
    flag = 1
    for j in range(len(T)):
        if s[j] == T[j] or s[j] == '?':
            pass
        else:
            flag = 0
    if flag:
        ans = S[0:i] + T + S[i+len(T)]
        ans = ans.replace('?', 'a')
print(ans)

### FIXED CODE ###

S = input()
T = input()

ans = 'UNRESTORABLE'
for i in range(len(S) - len(T) + 1):
    flag = 1
    for j in range(len(T)):
        if S[i+j] == T[j] or S[i+j] == '?':
            continue
        else:
            flag = 0
    if flag:
        ans = S[0:i] + T + S[i+len(T):]
        ans = ans.replace('?', 'a')
    
print(ans)
from collections import deque
def good(x,y):
    if (x>=0 and x<h) and (y>=0 and y<w):
        return (mat[x][y] != "#")
h, w = map(int,input().split())
sh, sw = map(int,input().split())
eh, ew = map(int,input().split())
mat = []
for _ in range(h):
    s = input()
    mat.append(s)
x = [1,-1,0,0]
y = [0,0,-1,1]
dist = [[float('inf') for i in range(w)]for j in range(h)]
sh -= 1
sw -= 1
eh -= 1
ew -= 1
dist[sh][sw] = 0
queue = deque()
queue.appendleft((sh,sw))
while queue:
    m = queue.popleft()
    for d in range(4):
        nx = m[0] + x[d]
        ny = m[1] + y[d]
        if good(nx,ny):
            if dist[nx][ny] > dist[m[0]][m[1]]:
                dist[nx][ny] =  dist[m[0]][m[1]]
                queue.appendleft((nx,ny))
    for i in range(m[0]-2,m[1]+3):
        for j in range(m[1]-2,m[1]+3):
            if good(i,j):
                if dist[i][j] > dist[m[0]][m[1]] + 1:
                    dist[i][j] = dist[m[0]][m[1]] + 1
                    queue.append((i,j))
if dist[eh][ew] == float('inf'):
    print(-1)
else:
    print(dist[eh][ew])


### FIXED CODE ###

n, x, t = map(int,input().split())

if n%x==0:
  print((n//x)*t)
else:
  n = n//x +1
  print(n*t)
from scipy.sparse.csgraph import csgraph_from_dense, bellman_ford
mINF = -(10**16)
n,m = map(int,input().split())
A = [0]*m
B = [0]*m
C = [0]*m
for i in range(m) :
    a, b, c = map(int,input().split())
    A[i], B[i], C[i] = a-1, b-1, -c

graph = [[mINF]*n for i in range(n)]
for i in range(m) :
    graph[A[i]][B[i]] = C[i]

graph = csgraph_from_dense(graph, null_value=mINF)
try :
    dist = bellman_ford(graph)
    print(-dist[0][n-1])
except : # NegativeCycleError in scipy
    ans = "inf"

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N,M = map(int,input().split())
edges = []
to = [[] for i in range(N)]
rto = [[] for i in range(N)]
for i in range(M) :
    u,v,cost = map(int,input().split())
    u -= 1
    v -= 1
    cost *= -1
    edges.append([u,v,cost])
    to[u].append(v)
    rto[v].append(u)

canVisitFromS = [False]*N
canVisitFromG = [False]*N

def dfs(u) :
    if canVisitFromS[u] : return
    canVisitFromS[u] = True
    for v in to[u] :
        dfs(v)

def rdfs(v) :
    if canVisitFromG[v] : return
    canVisitFromG[v] = True
    for u in rto[v] :
        rdfs(u)

dfs(0)
rdfs(N-1)

OK = [canVisitFromS[i] * canVisitFromG[i] for i in range(N)]

dist = [float("inf")]*N
dist[0] = 0

update = True
step = 0
ans = 0

while update :
    update = False
    for i in range(M) :
        u,v,cost = edges[i]
        if OK[u] * OK[v] == 0 : continue
        if dist[v] > dist[u] + cost :
            dist[v] = dist[u] + cost
            update = True
    step += 1
    if step > N :
        ans = "inf"
        break
if ans != "inf" :
    ans = dist[N-1] * (-1)
print(ans)
n,k=input().split();print(sum(sorted(int,input().split())[:int(k)]))

### FIXED CODE ###

n,k=input().split();print(sum(sorted(map(int,input().split()))[:int(k)]))
# coding: utf-8

def main():
    N = int(input())
    btc_to_jpy = 380000.0
    ans = 0
    for i in range(N):
        value,unit = map(int,input().split())
        if unit == "BTC":
            value *= btc_to_jpy
        ans += value
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding: utf-8

def main():
    N = int(input())
    btc_to_jpy = 380000.0
    ans = 0
    for i in range(N):
        temp_value,unit = input().split()
        value = float(temp_value)
        if unit == "BTC":
            value *= btc_to_jpy
        ans += value
    print(ans)

if __name__ == "__main__":
    main()
N, W, H = map(int, input().split())

print((N - W + 1) * (N - H + 1))


### FIXED CODE ###

N = int(input())
W = int(input())
H = int(input())

print((N - W + 1) * (N - H + 1))
import math
A,B = map(int, input().split())
print(int((A * B) / math.gcd(A, B)))

### FIXED CODE ###

from fractions import gcd
A,B = map(int, input().split())
print(int((A * B) / gcd(A, B)))
s = input().split()

for i in range(ord('a'), ord('z')+1):
 print("{0} : {1}".format(chr(i), s.count(chr(i)))

### FIXED CODE ###

import sys 
dataset = sys.stdin.readlines()

for s in range(ord('a'), ord('z') + 1):
 count = 0
 for data in dataset:
  count += data.lower().count(chr(s))
 print("{0} : {1}".format(chr(s), count))
import math
N,K = map(int,input().split())
if K > 10000:
  raise IndexError
cnt = 0
for n in range(1,N+1):
    if K/n <= 1:
        x = 0
    elif math.log(K/n)%math.log(2)<=0.00001:
        x = (math.log(K)-math.log(n))//math.log(2)
    else:
        x = (math.log(K)-math.log(n))//math.log(2)+1
    cnt += (0.5)**x
 
print(cnt/N)

### FIXED CODE ###

import math
N,K = map(int,input().split())
cnt = 0
for n in range(1,N+1):
    x = 0
    while n*(2**x) < K:
        x += 1
    cnt += (0.5)**x

print(cnt/N)
from math import factorial
def combi(n,r):
  res = factorial(n) / factorial(r) / factorial(n - r)
  return int(res)

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

data = {}

tmp = 0
for i in range(N):
  tmp += a[i]
  if tmp%M not in data:
    data[tmp%M] = 1
  else:
    data[tmp%M] += 1
else:
  data[0] += 1

cnt = list(data.values())
ans = 0
for i in cnt:
  if i == 1:
    continue
  else:
    ans += combi(i,2)
print(ans)

### FIXED CODE ###

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

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

S = {0 : 1}
t = 0
for i in range(N):
  t = (t + D[i]) % M
  if t in S:
    S[t] += 1
  else:
    S[t] = 1

r = 0

for i in S.values():
  r += i * (i - 1) // 2
  
print(r)
import sys
readline = sys.stdin.readline
n, m = map(int, input().split())
a = []
b = []
for _ in range(m):
    aa, bb = list(map(int, readline().split()))
    a.append(aa - 1)
    b.append(bb - 1)
a = a[::-1]
b = b[::-1]
ans = int(n * (n - 1) / 2)
ans_rec = [0] * m
ans_rec[-1] = ans
p = [-1] * n
size = [1] * n
def find(x):
    px = p[x]
    if px < 0:
        return x
    else:
        pxx = find(px)
        p[x] = pxx
        return pxx
for k in range(m - 1):
    pa = find(a[k])
    pb = find(b[k])
    if pa == pb:
        pass
    else:
        ans -= size[pa] * size[pb]
        size[pa] += size[pb]
        p[pb] = pa
    ans_rec[- k - 2] = ans
for aa in ans_rec:
    print(aa)


### FIXED CODE ###

import sys
readline = sys.stdin.readline
N, M = map(int, input().split())
ab = [tuple(map(lambda x: int(x) - 1, readline().split())) for _ in range(M)]
class UnionFind:
    def __init__(self, size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]
    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x
    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]
uf = UnionFind(N)
p = N * (N - 1) // 2
ans = [p]
for x, y in reversed(ab[1:]):
    px = uf.find(x)
    py = uf.find(y)
    if px != py:
        p -= uf.number[px] * uf.number[py]
        uf.union(px, py)
    ans.append(p)
print(*ans[::-1], sep="\n")
N, M = map(int, input().split())
A = []

for _ in range(M):
    a = int(input())
    A.append(a)

d = {}


def f(x):
    # print(d)
    if x in A:
        return 0
    if x > N:
        return 0
    if x == N:
        return 1

    if d.get(x):
        return d[x]

    # if d.get(x + 1):
    #     x1 = d.get(x + 1)
    # else:
    #     x1 = f(x + 1)
    #     d[x + 1] = x1
    #
    # if d.get(x + 2):
    #     x2 = d.get(x + 2)
    # else:
    #     x2 = f(x + 2)
    #     d[x + 2] = x2
    #
    # ans = x1 + x2
    ans = f(x + 1) + f(x + 2)
    d[x] = ans
    return ans


print(f(0) % 1000000007)


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    # print(ANS)
    # if x in A:
    #     print('::::', x)
    #     d[x] = 0
    #     return 0
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    # if d.get(x + 1):
    #     x1 = d.get(x + 1)
    # else:
    #     x1 = f(x + 1)
    #     d[x + 1] = x1
    #
    # if d.get(x + 2):
    #     x2 = d.get(x + 2)
    # else:
    #     x2 = f(x + 2)
    #     d[x + 2] = x2

    # ans = x1 + x2
    ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)
N, M = map(int, input().split())
A = [0 for i in range(N)]
B = [0 for i in range(N)]

for i in range(N):
  a,b = map(int, input().split())
  A[i] = a
  B[i] = b

ans = 0
count = 0
while(count < M):
  min_A = min(A)
  min_Ai = A.index(min_A)
  B_min = B[min_Ai]
  if count + B_min >= M:
    print(ans + min_A * (M - count))
    break
  else:
    ans += min_A * B_min
    count += B_min
    A.remove(min_A)
    B.remove(min_A)


### FIXED CODE ###

def unzip(li):
  return map(list, zip(*li))

N, M = map(int, input().split())
tmp_C = [0 for i in range(N)]

for i in range(N):
  a,b = map(int, input().split())
  tmp_C[i] = (a,b)
  
C = sorted(tmp_C)
A, B = unzip(C)
ans = 0
count = 0
cur = 0
while(count < M):
  min_A = A[cur]
  B_min = B[cur]
  if count + B_min >= M:
    print(ans + min_A * (M - count))
    break
  else:
    ans += min_A * B_min
    count += B_min
    cur += 1
import statistics
n = int(input())
x = list(map(int,input().split()))
a = x[:]
a.sort()
kijun = a[n//2]
a1 = a[n//2]
a2 = a[n//2-1]
for i in x:
	if i < kijun:
		print(a1)
	else:
		print(a2)

### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
a = x[:]
a.sort()
kijun = a[n//2]
a1 = a[n//2]
a2 = a[n//2-1]
for i in x:
	if i < kijun:
		print(a1)
	else:
		print(a2)
def main():
    from itertools import product

    H,W,K = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    
    i = 0
    while i < len(S):
        if '1' in S[i]:
            i += 1
        else:
            del S[i]
    H = len(S)
 
    S = [[int(s[i]) for s in S] for i in range(W)]

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = np.array([0]*len(M))
            for s in S:
                D[:] += [sum(s[i] for i in m) for m in M]
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    D[:] = [sum(s[i] for i in m) for m in M]
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()

### FIXED CODE ###


def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()
a, b, k = map(int, input().split())

if a < k :
	k = k - a
	a = 0	
	if b < k :
		b = 0
	else :
		b = b - k

else :
	a = a - k

print(a, b

### FIXED CODE ###

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

if a <= k :
	k = k - a
	a = 0	
	if b < k :
		b = 0
	else :
		b = b - k

else :
	a = a - k

print(a, b)
N = int(input())
ans = 0
lst = list(map(int, input().split()))
slice_lst = lst[:int(N / 2)]
for i,k in enumerate(reversed(slice_lst)):
  sub_lst = lst[len(slice_lst)-i-1:len(lst):len(slice_lst)-i]
  if (k != sum(sub_lst) % 2):
    if (k == 0):
      lst[len(slice_lst)-i-1] = 1
    else:
      ans = -1
      break

if (ans == -1):
  print(ans)
else:
  ans_lst = []
  for i,k in enumerate(lst):
    if (k == 1):
      ans_lst.append(str(i+1))
  print(len(ans_lst))
  result = ' '.join(ans_lst)
  print(result)

### FIXED CODE ###

r = int(input())

print(3 * r **2)
N, K, Q = map(int, input().split())
A = [int(input()) for i in range(N)]


def winner_or_loss(point):
    return 'Yes' if point > 0 else 'No'


def solve():
    point = [K-Q] * N

    for answer_id in A:
        answer_id -= 1
        point[answer_id] += 1

    return '\n'.join(list(map(winner_or_loss, point)))


print(solve())


### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]


def winner_or_loss(point):
    return 'Yes' if point > 0 else 'No'


def solve():
    point = [K-Q] * N

    for answer_id in A:
        answer_id -= 1
        point[answer_id] += 1

    return '\n'.join(list(map(winner_or_loss, point)))


print(solve())
import sys
input sys.stdin.readline

N_ken,M_si = map(int,input().split())
ken_year_map = {}
ken_year_list = []

for si in range(1,M_si+1):
    ken,year = map(int,input().split())
    ken_year_list.append([ken,year])
    if ken in ken_year_map:
        ken_year_map[ken].append(year)
    else:
        ken_year_map[ken] = [year]
for i in ken_year_map:
    ken_year_map[i].sort()

for ken,year in ken_year_list:
    print((str(ken*1000000 + ken_year_map[ken].index(year)+1)).zfill(12))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect

N_ken,M_si = map(int,input().split())
ken_year_map = {}
for i in range(1,N_ken+1):ken_year_map[i]=[]

ken_list = [0]*M_si
year_list = [0]*M_si

for si in range(M_si):
    ken_list[si],year_list[si] = map(int,input().split())
    ken_year_map[ken_list[si]] += [year_list[si]]
        
for i in ken_year_map:
    ken_year_map[i].sort()

for ken,year in zip(ken_list,year_list):
    print('{:06}{:06}'.format(ken,bisect.bisect_right(ken_year_map[ken], year)))
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
for j in B:
    OK = -1
    NG = N
    while abs(OK-NG) > 1:
        mid = (OK + NG) // 2
        print(mid)
        if A[mid] < j:
            OK = mid
        else:
            NG = mid
    A_ko = mid
        
    left_f = -1
    right_t = N+1
    while abs(left-right) > 1:
        mid = (left + right) // 2
        if C[mid] > j:
            left_f = mid
        else:
            right_t = mid
C_ko = mid 
ans += A_ko*C_ko
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
for j in B:
    OK = -1
    NG = N
    while abs(OK-NG) > 1:
        mid = (OK + NG) // 2
        if A[mid] < j:
            OK = mid
        else:
            NG = mid
    A_ko = OK
    #print(OK)
        
    NG = -1
    OK = N
    while abs(NG-OK) > 1:
        mid = (NG + OK) // 2
        if C[mid] > j:
            OK = mid
        else:
            NG = mid
    
    C_ko = N - OK
    #print(C_ko)
    ans += (A_ko+1)*C_ko

print(ans)
def main():
    sum, leg = map(int, input().split())
    


    for i in range(sum):
        for x in range(sum - i):
            crane = i * 2
            turtle = x * 4
            total = crane + turtle
            if total == leg:
                print('Yes')
                return
    print('No')
    
main()

### FIXED CODE ###

def main():
    l = list(map(int, input().split()))
    for i in range(len(l)):
        if l[i] == 0:
            print(i + 1)
            return
    
main()
#<14>
#(point)
#全探索によってどの建物が見えるようにするかを決めて必要な費用を計算。
#建物が見える =　それより左にある建物maxより１大きいなので左から線形に
#最大値を更新、計算量は高々n_c_kのcombについてO(N)の操作なのでおｋ
from itertools import combinations
n, k = map(int,input().split())
a = list(map(int,input().split()))
mn = 10 ** 18

for b in combinations(range(1, n),k - 1):#一番左は固定
    mx = a[0] #初期値=一番左の建物
    score = 0
    for j in range(1, n):
        if j in b:#見えなあかん建物なら
            if a[j] <= mx : #低けりゃ高くする
                mx += 1
                score += (mx - a[j])
            else: #高さが十分なら最大値を更新するだけ
                mx = a[n]
        else:
            mx = max(mx, a[j])#別に見えんくてもいい建物なら最大値更新
    mn = min(mn, score)
print(mn)
                


### FIXED CODE ###


2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from itertools import combinations
N, K = map(int, input().split())
A = list(map(int, input().split()))
mn = 10**18
for B in combinations(range(1,N),K-1): # 一番左は固定
    mx = A[0] # 初期値は一番左の建物
    score = 0
    for n in range(1,N):
        if n in B: # 見えるようにすべき建物なら
            if A[n] <= mx: # 低ければ高くする
                mx += 1
                score += (mx - A[n])
            else: # 高さが十分なら何もしない。最大値を更新
                mx = A[n]
        else:
            mx = max(mx, A[n]) # 見えなくても良い建物なら、最大値を更新
    mn = min(mn, score)
print (mn)