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

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

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	#d = defaultdict(int)
	d = dict()
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		dels = []
		if a[i] < a[i+1]:
			last = a[i+1]
			continue

		for k in d.keys():
			if last < k:
				dels.append(k)

		j = a[i+1]
		while j > 0:
			if j in d and d[j] == x-1:
				d[j] = 0
				dels.append(j)
				j -= 1
			else:
				break

		if j in d:
			d[j] += 1
		else:
			d[j] = 1

		for k in dels:
			del d[k]

		if 0 in d:
			valid = False
			break
		last = j

	if valid:
		ok = x
	else:
		ng = x
print(ok)

### FIXED CODE ###

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

ok, ng = n, 0
while ok-ng > 1:
	x = (ok+ng)//2
	#d = defaultdict(int)
	d = dict()
	last = 0
	valid = True
	if x == 1:
		for i in range(n-1):
			if a[i] >= a[i+1]:
				valid = False
				break
		if valid:
			ok = x
		else:
			ng = x
		continue

	for i in range(n-1):
		dels = []
		if a[i] < a[i+1]:
			last = a[i+1]
			continue

		j = a[i+1]
		for k in d.keys():
			if j < k:
				dels.append(k)

		while j > 0:
			if j in d and d[j] == x-1:
				#d[j] = 0
				dels.append(j)
				j -= 1
			else:
				break

		if j in d:
			d[j] += 1
		else:
			d[j] = 1

		for k in dels:
			del d[k]

		if 0 in d:
			valid = False
			break
		last = j

	if valid:
		ok = x
	else:
		ng = x
print(ok)
### BUGGY CODE ###

s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    r_0 = int(s[-1]) % 13
    dp[0][r_0] += 1
else:
    for k in range(10):
        r_0 = k % 13
        dp[0][r_0] += 1

for i in range(1,len(s)):
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10):
                j = (k * (10**i) + r) % 13
                dp[i][j] += dp[i-1][r]
        else:
            j = (int(s[-(i+1)]) * (10**i) + r) % 13
            dp[i][j] += dp[i-1][r]
            
print(dp[len(s)-1][5]%(10**9+7))


### FIXED CODE ###

s = input()
dp = [[0 for i in range(13)]]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    dp.append([0]*13)
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

print(dp[len(s)-1][5]%(10**9+7))
### BUGGY CODE ###

N,M=map(int,input().split())
all=[]
for i in range(M):
    L,R=map(int,input().split())
    if i==0:
        ans=[b for b in range(L,R+1)]
    else:
        ids=[b for b in range(L,R+1)]
        ans=set(ans)&set(ids)
print(len(ans))

### FIXED CODE ###

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

def solve(i,m,A):
    global n
    if m == 0 :
        return True
    elif i >= n :
        return False
    elif m < 0:
        return False
    else:
        return (solve(i+1,m,A) or solve(i+1,m-A[i],A))

global n
n = int(input())
st = input()
A = list(map(int,st.split()))
# dont use q(num of ans patarn) dumping!
input()
st = input()
ans = list(map(int,st.split()))

for x in ans:
    if(solve(0,x,A) == True):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

is_able_make = [False]*2000

input()

A = [ int( val ) for val in input().rstrip().split( ' ' ) ]
q = int(input())
M = [ int( val ) for val in input().rstrip().split( ' ' ) ]

for i in A:
    for j in range(2000-i,0,-1):
        if is_able_make[j] == True:
            is_able_make[i+j] = True
    is_able_make[i] = True

for x in M:
    if(is_able_make[x] == True):
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i): 
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    for i in range(N):
         if a[i]>=K:
             break
         ss[i+1]=mkns(a[i],ss[i],pm)
         if isunnec(i):
             nn+=1
        # for j in range(i+1,N):
        #     if a[j]>=K:
        #         break
        #     ss[i]=mkns(a[j],ss[i],pm)
        # # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        # if ss[i]&mask(K-a[i])==0:
        #     nn+=1
    # nn=biser(list(range(N)),isunnec)+1
    # print(list(map(bin,ss)))
    print(nn)

if __name__=='__main__':
    main()


### FIXED CODE ###

#4 9
#1 3 5 6
#の時に1（正解は0）と出力されるがACになる

N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a_and_b_list = [list(map(int, input().split())) for _ in range(m)]
bridge_broken = [False for _ in range(n-1)]
a_and_b_list.sort(key=lambda x: x[1])
for a_and_b in a_and_b_list:
    if True not in bridge_broken[a_and_b[0]-1:a_and_b[1]-1]:
        bridge_broken[a_and_b[1]-2] = True
print(bridge_broken.count(True))

### FIXED CODE ###

n, m = map(int, input().split())
a_and_b_list = [list(map(int, input().split())) for _ in range(m)]
bridge_broken = [False for _ in range(n-1)]
a_and_b_list.sort(key=lambda x: x[1])
previous_broken_bridge = -1
for a_and_b in a_and_b_list:
    if previous_broken_bridge < a_and_b[0]:
        bridge_broken[a_and_b[1]-2] = True
        previous_broken_bridge = a_and_b[1] - 1
print(bridge_broken.count(True))
### BUGGY CODE ###

N,K=map(int,input().split())
mod=1000000007
path=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  path[a].append(b)
  path[b].append(a)
#print(path)
  
abc=[0 for i in range(N)] #0ならまだ塗ってない

abc[0]=1
cnt=0
ans=K
nx=[]
for i in range(len(path[0])):
  child=path[0][i]
  if abc[child]==0:
    ans=ans*(K-1-cnt)
    cnt=cnt+1
    abc[child]=1
    nx.append(child)
while len(nx)>0:
  a=nx.pop(0)
  cnt=0
  for i in range(len(path[a])):
    child=path[a][i]
    if abc[child]==0:
      ans=ans*(K-2-cnt)
      cnt=cnt+1
      abc[child]=1
      nx.append(child)
      
print(ans%mod)
      
      
    

### FIXED CODE ###

N,K=map(int,input().split())
mod=1000000007
path=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  path[a].append(b)
  path[b].append(a)
#print(path)
  
abc=[False for i in range(N)] #0ならまだ塗ってない

abc[0]=True
cnt=0
ans=K%mod
nx=[]
for i in range(len(path[0])):
  child=path[0][i]
  if abc[child]:
    continue
  ans=ans*(K-1-cnt)
  ans=ans%mod
  cnt=cnt+1
  abc[child]=True
  nx.append(child)
while len(nx)>0:
  a=nx.pop()
  cnt=0
  for i in range(len(path[a])):
    child=path[a][i]
    if abc[child]:
      continue
    ans=ans*(K-2-cnt)
    ans=ans%mod
    cnt=cnt+1
    abc[child]=True
    nx.append(child)
      
print(ans%mod)
### BUGGY CODE ###

h,w,m=[int(i) for i in raw_input().split()]
r=[0 for i in range(h)]

c=[0 for i in range(w)]
d={}
for i in range(m):
    h1,w1=[int(i)-1 for i in raw_input().split()]
    r[h1]+=1
    c[w1]+=1
    x=str(h1)+"#"+str(w1)
    d[x]=d.get(x,0)+1
maxx=0
for i in range(h):
    for j in range(w):
        x=str(i)+"#"+str(j)
        maxx=max(maxx,r[i]+c[j]-d.get(x,0))
print maxx


### FIXED CODE ###

h,w,m=[int(i) for i in raw_input().split()]
r=[0 for i in range(h)]
c=[0 for i in range(w)]
d={}
for i in range(m):
    h1,w1=[int(j)-1 for j in raw_input().split()]
    r[h1]+=1
    c[w1]+=1
    x=str(h1)+'#'+str(w1)
    d[x]=d.get(x,0)+1
maxx=max(r)
r1=[]
for i in range(len(r)):
    if maxx==r[i]:
        r1.append(i)
maxx=max(c)
c1=[]
for i in range(len(c)):
    if maxx==c[i]:
        c1.append(i)
maxx1=0;flag=0
for i in r1:
    for j in c1:
        x=str(i)+'#'+str(j)
        if(d.get(x,0)==0):
            maxx1=max(maxx1,r[i]+c[j])
            flag=1
        else:
            maxx1=max(maxx1,r[i]+c[j]-d[x])
    if flag:
        break
print maxx1
### BUGGY CODE ###

# const
M = 6094397

def h1(key):
    return key % M

def h2(key):
    return 1 + (key % (M-1))

def hash(key ,i):
    return (h1(key) + i*h2(key)) % M

def conv_str_to_num(str):
    converted = 0
    s_list = list(str)
    for (i,c) in enumerate(s_list):
        if c == 'A':
            n = 1
        elif c == 'C':
            n = 2
        elif c == 'G':
            n = 3
        elif c == 'T':
            n = 4
        else:
            n = 0

        converted += 5**i * n

    return converted



class hashTable(object):
    def __init__(self, arg):
        self.T = [""] * arg

    def insert(self, s):
        key = conv_str_to_num(s)
        i = 0
        while True:
            h = hash(key, i)
            if self.T[h] == "":
                self.T[h] = s
                break
            i += 1

    def find(self, s):
        key = conv_str_to_num(s)
        i = 0
        while True:
            h = hash(key, i)
            if self.T[h] == s:
                return 1
            elif self.T[h] == "":
                return 0

            i += 1
        return 0


if __name__ == '__main__':
    h_t = hashTable(M)
    n = int(input())
    for _ in range(n):
        op, s = input().split()
        if op == "insert":
            h_t.insert(s)
        else:
            tmp = h_t.find(s)
            if tmp == 1:
                print("yes")
            else:
                print("no")

### FIXED CODE ###

def hash1(m, key):
    return key % m

def hash2(m, key):
    return 1 +  key % (m - 1)

def hash(m, key, i):
    return (hash1(m, key) + i * hash2(m, key) ) % m

def insert(T, key):
    i = 0
    l = len(T)
    while True:
        h = hash(1046527,key,i)
        if (T[h] == None ):
            T[h] = key
            return h
        elif (T[h] == key):
            return h
        else:
            i += 1

def search(T,key):
    l = len(T)
    i = 0
    while True:
        h = hash(1046527,key,i)
        if(T[h] == key):
            return h
        elif(T[h] is None or h >= l):
            return -1
        else:
            i += 1

def find(T, key):
    a = search(T,key)
    if(a == -1):
        print('no')
    else:
        print('yes')

dict = {'A' : '1', 'C' : '2', 'G' : '3', 'T' : '4'}
data = []
T = [None]*1046527
n = int(input())


while n > 0:
    st = input()
    d = list(st.split())

### convert key to num(1~4)
    tmp_key = ''
    for x in list(d[1]):
        tmp_key += dict[x]

    data.append([d[0],int(tmp_key)])
    n -= 1
for com in data:
    if(com[0] == 'insert'):
        insert(T,com[1]) 
    else:
        find(T,com[1])
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int,input().split())
sth, stw = map(int,input().split())
glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
direc5 = set([])
for i in range(-2,3):
    for j in range(-2,3):
        direc5.add((i, j))
direc5 = direc5 - direc
direc5 = direc5 - {(0,0)}
nxt_st = set([])

def bfs(pnxt):
    next_q = deque([])
    for hw in pnxt:
        next_q.append(hw)
    nxt = set([])
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h,w = next_q.popleft()
        if h == glh and w == glw:
            print(ret)
            exit()
        seen[h][w] = 0
        for dh, dw in direc:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                next_q.append((hs, ws))
                seen[hs][ws] = 0
        for dh, dw in direc5:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                nxt.add((hs, ws))

    return nxt

ret = -1
nxt_st.add((sth, stw))
while len(nxt_st)>0:
    ret += 1
    nxt_st = bfs(nxt_st)
print(-1)


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int,input().split())
sth, stw = map(int,input().split())
glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
direc5 = set([])
for i in range(-2,3):
    for j in range(-2,3):
        direc5.add((i, j))
direc5 = direc5 - direc
direc5 = direc5 - {(0,0)}

def bfs(pnxt):
    next_q = deque([])
    for h, w in pnxt:
        next_q.append((h,w))
        seen[h][w] = 0
    nxt = set([])
    while len(next_q)!=0:
        h, w = next_q.popleft()
        if h == glh and w == glw:
            print(ret)
            exit()
        for dh, dw in direc:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                next_q.append((hs, ws))
                seen[hs][ws] = 0
        for dh, dw in direc5:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF and not (hs, ws) in nxt:
                nxt.add((hs, ws))
    return nxt

ret = 0
nxt_st = set([])
nxt_st.add((sth, stw))
while len(nxt_st)>0:
    nxt_st = bfs(nxt_st)
    ret += 1
print(-1)
### BUGGY CODE ###

def calc():
 N,M = map(int,input().split())
 gcd = M // N
 gcd_tmp = 0
 while gcd > 0:
  tmp = M - gcd
  if tmp % gcd == 0:
   break
  gcd = gcd - 1
 return(gcd)
print(calc())

### FIXED CODE ###

def calc():
 N,M = map(int,input().split())
 for gcd in range(M // N,0,-1):
  if M % gcd == 0:
   break
 return(gcd)
print(calc())
### BUGGY CODE ###

INF = int(1e18)


def main():
    input()
    *A, = map(int, input().split())
    ans = 1
    for a in A:
        ans *= a
    print(-1 if INF < ans else ans)
    return


main()


### FIXED CODE ###

INF = int(1e18)


def main():
    N, *A, = map(int, open(0).read().split())
    ans = 1
    if 0 in A:
        print(0)
        return
    for a in A:
        ans *= a
        if INF < ans:
            print(-1)
            break
    else:
        print(ans)
    return


main()
### BUGGY CODE ###

n = int(input())
s = [0]*n

for i in range(n):
  s[i] = input()
  
a = []
b = []
for i in range(n):
  if s[i] not in a:
    a.append(s[i])
    
print(len(a))

### FIXED CODE ###

n = int(input())
s = [0]*n

for i in range(n):
  s[i] = input()
ans = 0
s.sort()
for i in range(n-1):
  if s[i] != s[i+1]:
    ans += 1
    
print(ans+1)
### BUGGY CODE ###

s=input()
s=s[::-1]
#print(s) #並び替え
n=len(s)
 
count=[0]*2019
count[0]=1
num,d=0,1
 
for i in s:
  num+=int(i)*d
  #print(d)
  #print(i,num)
  num%=2019
  d*=10
  #print(num)
  #d%=2019
  count[num]+=1
  
ans=0
for i in count:
  ans+=i*(i-1)//2
  
print(ans)

### FIXED CODE ###

s=input()
s=s[::-1]
n=len(s)
 
count=[0]*2019
count[0]=1
num,d=0,1
 
for i in s:
  num+=int(i)*d
  num%=2019
  d*=10
  d%=2019
  count[num]+=1
 
ans=0
for i in count:
  ans+=i*(i-1)//2
  
print(ans)
### BUGGY CODE ###

import copy, itertools
from scipy.sparse.csgraph import floyd_warshall

N, M, R = map(int, input().split())
r = [x-1 for x in list(map(int, input().split()))]

way_cost = [[float('inf')]*N for _ in range(N)]

for idx in range(N):
    way_cost[idx][idx] = 0

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

# ワーシャルフロイド法で全ての街同士の最短距離を求める
shortest_path_cost = copy.deepcopy(way_cost)
for between_point in range(N):
    for start_point in range(N):
        for end_point in range(N):
            shortest_path_cost[start_point][end_point] \
                = min(shortest_path_cost[start_point][end_point],
                      shortest_path_cost[start_point][between_point]+shortest_path_cost[between_point][end_point])

# 巡回ルートを総当りで調べ、最小コストを出力する
route_list = list(itertools.permutations(r))

ans = float('inf')
for route in route_list:
    cost = 0
    for idx in range(R-1):
        cost += shortest_path_cost[route[idx]][route[idx+1]]
    ans = min(ans,cost)

print(int(ans))


### FIXED CODE ###

import copy, itertools
from scipy.sparse.csgraph import floyd_warshall

N, M, R = map(int, input().split())
r = [x-1 for x in list(map(int, input().split()))]

way_cost = [[float('inf')]*N for _ in range(N)]

for idx in range(N):
    way_cost[idx][idx] = 0

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

# ワーシャルフロイド法で全ての街同士の最短距離を求める
shortest_path_cost = floyd_warshall(csgraph=way_cost, directed=False)

# 巡回ルートを総当りで調べ、最小コストを出力する
route_list = list(itertools.permutations(r))

ans = float('inf')
for route in route_list:
    cost = 0
    for idx in range(R-1):
        cost += shortest_path_cost[route[idx]][route[idx+1]]
    ans = min(ans,cost)

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

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

arr=list(map(int,input().split()))
inf =1e9+5
dp = [inf]*(n)

dp[0] = 0

for i in range(n):
    for j in range(i+1,i+k+1):
        if j < n:
            dp[j] = min(dp[j],dp[i]+abs(arr[i]-arr[j]))
            
            
print(dp[n-1])

### FIXED CODE ###

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

arr=list(map(int,input().split()))
inf =1e9+5
dp = [inf]*(n)

dp[0] = 0

for i in range(n):
    for j in range(i+1,i+k+1):
        if j < n:
            dp[j] = min(dp[j],dp[i]+abs(arr[i]-arr[j]))
            
            
print(dp[n-1])
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
MOD = 1000000007
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        continue
        
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
        
print(dp[n])

### FIXED CODE ###

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
MOD = 1000000007
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0
    
for i in range(2,n+1):
    if i in a:
        continue
        
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
        
print(dp[n])
### BUGGY CODE ###

from collections import deque
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,q = map(int,readline().split())
ki = [[] for _ in range(n)]

for i in range(n-1):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    ki[a].append(b)
    ki[b].append(a)

count = [0]*n
for j in range(q):
    p,x = map(int,readline().split())
    p -= 1
    count[p] += x

queue = deque([[0,count[0]]])
already = [0]
while queue:
    x,q = queue.pop()
    already.append(x)
    for i in ki[x]:
        if not i in already:
            count[i] += q
            queue.append([i,count[i]])
        


print(*count)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q = map(int,readline().split())
AB = [list(map(int,readline().split())) for i in range(N-1)]

graph = [[] for _ in range(N+1)] #隣接リスト
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

#親のノードに子を入れてくdfs
stack = [1]
parent = [0]*(N+1)
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in graph[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)

query = [0]*(N+1)

for i in range(Q):
    p,x = map(int,readline().split())
    query[p] += x

#全ての親についての累積和を取る。
#この時、親方向に逆流しないように注意。
for x in order:
    a = query[x]
    for y in graph[x]:
        if y == parent[x]: #逆流防止弁
            continue
        query[y] += a

print(*query[1:])
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0 for _ in range(n)]

for i in range(n):
  for j in range(1, min(i, k)+1):
    if dp[i] == 0:
      dp[i] = dp[i-j]+abs(h[i]-h[i-j])
    else:
      dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]), dp[i])
print(dp[-1])

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
h = np.array(list(map(int, input().split())))
dp = np.array([0 for _ in range(n)])
dp[0] = 0
for i in range(1, n):
  j = max(0, i-k)
  dp[i] = min(dp[j:i] + np.abs(h[i]-h[j:i]))

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

def main():
    s = input()
    m = 1
    t = [None]*m
    t[0] = 0
    for i in s:
        t2 = [[] for _ in [0]*m]
        for j in range(m):
            k = t[j]
            if k is None:
                continue
            if i != "1":
                t2[max(j-1, 0)].append(k-1)
            if i != "0":
                if j+1 < m:
                    t2[j+1].append(min(0, k+1))
                else:
                    t2.append([min(0, k+1)])
                    t.append(None)
                    m += 1
        for j in range(m):
            if t2[j]:
                t[j] = max(t2[j])
            else:
                t[j] = None
        for i in range(m-1, 1, -1):
            if t[i] == t[i-1]:
                t[i] = None
            if t[i] == t[i-2]:
                t[i] = None
        for i in range(m-1, -1, -1):
            if t[i] is None:
                t.pop()
                m -= 1
            else:
                break

    ans = 10**10
    for i in range(m):
        if t[i] is not None:
            ans = min(ans, i-t[i])
    print(ans)


main()

### FIXED CODE ###

def main():
    S = input()
    size = [[[[0, 0]], []], [[], []]]
    length = 0

    for s in S:
        size2 = [[[], []], [[], []], [[], []]]
        if s != "0":
            for i in range(2):
                for j in range(2):
                    if size[i][j]:
                        for x, y in size[i][j]:
                            if y == length+i:
                                size2[i+1][j ^ 1].append([y+1, y+1])
                                if x != y:
                                    size2[i][j ^ 1].append([x+1, y-1])
                            else:
                                size2[i][j ^ 1].append([x+1, y+1])
        if s != "1":
            for i in range(2):
                for j in range(2):
                    if size[i][j]:
                        for x, y in size[i][j]:
                            if x == 0:
                                size2[i+1][j].append([0, 0])
                                if x != y:
                                    size2[i][j ^ 1].append([x+1, y-1])
                            else:
                                size2[i][j ^ 1].append([x-1, y-1])
        if len(size2[0][0]+size2[0][1]) == 0:
            size2 = size2[1:]
            length += 1
        else:
            size2.pop()
        for i in range(2):
            for j in range(2):
                size2[i][j] = sorted(size2[i][j])
        size = [[[], []], [[], []]]
        for i in range(2):
            for j in range(2):
                if len(size2[i][j]) == 0:
                    continue
                elif len(size2[i][j]) == 1:
                    size[i][j] = size2[i][j]
                    continue
                size[i][j] = [size2[i][j][0]]
                for x, y in size2[i][j][1:]:
                    p, q = size[i][j][-1]
                    if y <= q:
                        continue
                    if x <= q+2:
                        size[i][j][-1][1] = y
                    else:
                        size[i][j].append([x, y])
    print(length)


main()