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

import sys,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n = onem()

a = l()

b = l()

t = []

for i in range(n):
    if b[i] != a[i]:
        hq.heappush(t,[-b[i],i])
hq.heapify(t)
co = 0
while t:
    k = hq.heappop(t)
    k = [-k[0],k[1]]
    if k[1] == 0:
        ppp = (k[0]-a[k[1]]) // (b[-1] + b[1])
        if ppp == 0:
            print(-1)
            exit()
        co += ppp
        k[0] = (k[0]-a[k[1]]) % (b[-1] + b[1]) + a[k[1]]
    elif k[1] == n-1:
        ppp = (k[0]-a[k[1]]) // (b[-2] + b[0])
        if ppp == 0:
            print(-1)
            exit()
        co += ppp
        k[0] = (k[0]-a[k[1]]) % (b[-2] + b[0]) + a[k[1]]
    else:
        ppp = (k[0]-a[k[1]]) // (b[k[1]+1] + b[k[1]-1])
        if ppp == 0:
            print(-1)
            exit()
        co += ppp
        k[0] = (k[0]-a[k[1]]) % (b[k[1]+1] + b[k[1]-1]) + a[k[1]]
    b[k[1]] = k[0]
    if b[k[1]] != a[k[1]] and len(t) != 0:
        hq.heappush(t,[-b[k[1]],k[1]])

print(co)

### FIXED CODE ###

import heapq as hq
mod = 10**9+7
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())

def onon():
    n = onem()

    a = l()

    b = l()

    t = []

    for i in range(n):
        if b[i] != a[i]:
            hq.heappush(t,(-b[i],i))
    co = 0
    while t:
        k = hq.heappop(t)
        k = (-k[0],k[1])
        q,w = divmod(k[0] - a[k[1]], b[(k[1] - 1) % n] + b[(k[1] + 1) % n])
        co += q
        if q == 0:
            return -1
        w = a[k[1]] + w
        b[k[1]] = w
        if b[k[1]] != a[k[1]]:
            hq.heappush(t,(-w,k[1]))
    return co
print(onon())
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())

G = []
for i in range(N):
 a, b, c = map(int, input().split())
 G.append( (a,b,c) )

M = 401
INF = 1000000000
dp = {}
for i in range(M):
  for j in range(M):
    dp[i,j] = INF
dp[0,0] = 0
for a, b, c in G:
  for i in reversed(range(0, M - a)):
    for j in reversed(range(0, M - b)):
      dp[i+a,j+b] = min(dp[i+a,j+b], dp[i,j] + c)

ans = INF
x = 1
while Ma * x < M and Mb * x < M:
  ans = min(ans, dp[Ma * x,Mb * x])
  x += 1
if ans >= INF:
  ans = -1
print(ans)


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())

G = []
for i in range(N):
 a, b, c = map(int, input().split())
 G.append( (a,b,c) )

M = 1 + min(sum([ a for a, b, c in G ]),
            sum([ b for a, b, c in G ]) )
INF = 1000000000
dp = [INF] * (M * M)
dp[0] = 0
for a, b, c in G:
  i = M - a - 1
  while i >= 0:
    j = M - b - 1
    while j >= 0:
      dp[(i+a)*M+(j+b)] = min(dp[(i+a)*M+(j+b)], dp[i*M+j] + c)
      j -= 1
    i -= 1

ans = INF
x = 1
while Ma * x < M and Mb * x < M:
  ans = min(ans, dp[Ma * x * M + Mb * x])
  x += 1
if ans >= INF:
  ans = -1
print(ans)
### BUGGY CODE ###

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

m = 10 ** 9 + 7
def main():
    r = 0
    for i in range(int(n / 2)):
        r += ((a[i] % m) * (sum(a[i+1:]) % m))
    
    for i in range(int(n / 2), n-1):
        r += ((a[i] % m) * (sum(a[i+1:]) % m))
    print(r % m)
    return

main()


### FIXED CODE ###

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


m = 10 ** 9 + 7
def main():
    s = sum(a)
    ss = 0
    r = 0
    for nn in range(n):
        ss += a[nn]
        r += a[nn] * (s - ss)
    print(r % m)
    return

main()
### BUGGY CODE ###

# 未完成　要素と個数を別にしてソートすればいける？
import numpy as np
N, M = map(int, input().split())
A = sorted([int(x) for x in input().split()])
card = np.zeros(N)
for i in range(N):
    card[i] = A[i]

for j in range(M):
    B, C = map(int, input().split())
    for k in range(B):
        card = np.append(card, C)
card = sorted(card, reverse=True)

ans = 0
for h in range(N):
    ans += card[h]
print("{}".format(int(ans)))


### FIXED CODE ###

# 未完成　要素と個数を別にしてソートすればいける？
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
cardnumberlist = []
card_dict = {}
for i in range(N):
    if A[i] in card_dict:
        card_dict[A[i]] += 1
    else:
        card_dict[A[i]] = 1
        cardnumberlist.append(A[i])

for j in range(M):
    B, C = map(int, input().split())
    if C in card_dict:
        card_dict[C] += B
    else:
        card_dict[C] = B
        cardnumberlist.append(C)
ans = 0
cardnumberlist = sorted(cardnumberlist, reverse=True)
# print(cardnumberlist)
# print(card_dict)
numofcard = 0
for h in range(N):
    #print(h)
    if numofcard + card_dict[cardnumberlist[h]] > N:
        ans += cardnumberlist[h] * (N - numofcard)
        break
    else:
        ans += cardnumberlist[h] * card_dict[cardnumberlist[h]]
        numofcard += card_dict[cardnumberlist[h]]
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

data = input().split()
n = int(data[0])
m = int(data[1])
edge=[]
for i in range(m):
    tmp = []
    data = input().split()
    tmp.append(int(data[0])-1)
    tmp.append(int(data[1])-1)
    edge.append(tmp)

grp=list(range(0, n))
def group(num):
    if grp[num] == num:
        return num
    return group(grp[num])

def merge(num1, num2):
    grp[num2]=grp[num1]

res=[]
ans = [1]*n
ben = int(n*(n-1)/2)
edge.reverse()
for e in edge:
    #print(e, ans, ben, grp)
    res.append(ben)
    g0 = group(e[0])
    g1 = group(e[1])
    if g0 != g1:
        ben -= ans[g0]*ans[g1]
        sum = ans[g0]+ans[g1]
        merge(g0, g1)
        ans[g0]=sum
        ans[g1]=sum

res.reverse()
for r in res:
    print(r)

#print(int(n*(n-1)/2))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

data = input().split()
n = int(data[0])
m = int(data[1])
edge=[]
for i in range(m):
    tmp = []
    data = input().split()
    tmp.append(int(data[0])-1)
    tmp.append(int(data[1])-1)
    edge.append(tmp)

grp=list(range(0, n))
def group(num):
    if grp[num] == num:
        return num
    return group(grp[num])

def merge(p_num, c_num):
    grp[c_num]=grp[p_num]

res=[]
ans = [1]*n
ben = int(n*(n-1)/2)
edge.reverse()
for e in edge:
    #print(e, ans, ben, grp)
    res.append(ben)
    g0 = group(e[0])
    g1 = group(e[1])
    if g0 != g1:
        ben -= ans[g0]*ans[g1]
        sum = ans[g0]+ans[g1]
        if ans[g0] > ans[g1]:
            merge(g0, g1)
        else:
            merge(g1, g0)
        ans[g0]=sum
        ans[g1]=sum

res.reverse()
for r in res:
    print(r)

#print(int(n*(n-1)/2))
### BUGGY CODE ###

X = int(input())

for i in range(X, 0, -1):
    tmp = i
    while tmp <= X:
        tmp *= tmp
    if tmp == X:
        print(i)


### FIXED CODE ###

X = int(input())

ans = 1
for i in range(1, X):
    for j in range(2, X):
        tmp = i ** j
        if tmp > X:
            break
        ans = max(tmp, ans)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

S=input()[:-1]
Q=int(input()[:-1])
f=0

for _ in range(Q):
    q=input().split()
    if int(q[0])==1:
        f = (f+1)%2
    if int(q[0])==2:
        if int(q[1])==1:
            if f==0:
                S=q[2]+S
            else:
                S=S+q[2]
        else:
            if f==0:
                S=S+q[2]
            else:
                S=q[2]+S
if f==0:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

S=list(input()[:-1])
Q=int(input()[:-1])
f=0
back=[]
forward=[]

for _ in range(Q):
    q=input().split()
    if int(q[0])==1:
        f = (f+1)%2
    if int(q[0])==2:
        if int(q[1])==1:
            if f==0:
                forward.append(q[2])
            else:
                back.append(q[2])
        else:
            if f==0:
                back.append(q[2])
            else:
                forward.append(q[2])

if f==0:
    print("".join(forward[::-1]+S+back))
else:
    print("".join((forward[::-1]+S+back)[::-1]))
### BUGGY CODE ###

import queue
import numpy
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        row=input()
        r_append(row)
    #print(maze)
    root=numpy.array([[-1 for i in range(h*w)] for i in range(h*w)])
    ina=numpy.array([i for i in range(h*w)])
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    hw=h*w
    for start in range(hw):
        if ina[start]==-1:
           # print(start,"is unreachable")
            continue
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=queue.Queue()
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                toVis.put(i)
                dist[i]=dist[now]+1
        while toVis.empty()!=True:
            now=toVis.get()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    toVis.put(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()


    
            

### FIXED CODE ###

h,w=map(int,input().split())
n=h*w
inf=10**6
field=[]
for i in range(h):
    field.append(input())
dist=[[inf]*n for i in range(n)]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":continue
        if j+1<w and field[i][j+1]!="#":
            dist[i*w+j][i*w+j+1]=1
            dist[i*w+j+1][i*w+j]=1
        if i+1<h and field[i+1][j]!="#":
            dist[i*w+j][(i+1)*w+j]=1
            dist[(i+1)*w+j][i*w+j]=1
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k])
ans=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if dist[i][j]==inf:
            continue
        ans=max(ans,dist[i][j])
print(ans)
### BUGGY CODE ###

number = int(input())
count = 0

for i in range(number):
  for j in range(number,1, -1):
    temp = number - i*j
    if temp > 0:
      count += 1

print(count)
  


### FIXED CODE ###

number = int(input())
count = 0

for i in range(1,number):
  temp = number -1
  temp_solution = int(temp/i)
  count += temp_solution
print(count)
### BUGGY CODE ###

N,Q = map(int,input().split())
STX = [tuple(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

starts = []
ends = []
for i,(s,t,x) in enumerate(STX):
    starts.append((s-x,i))
    ends.append((t-x,i))
starts.sort(reverse=True)
ends.sort(reverse=True)

import heapq
hq = []
heapq.heapify(hq)
delset = set()

ans = []
for d in D:
    while starts and starts[-1][0] <= d:
        _,i = starts.pop()
        x = STX[i][2]
        heapq.heappush(hq, (x,i))
    while ends and ends[-1][0] <= d:
        _,i = ends.pop()
        delset.add(i)
    while hq:
        _,i = hq[0]
        if i in delset:
            heapq.heappop(hq)
        else:
            break
    if len(hq)==0:
        ans.append(-1)
    else:
        x,i = hq[0]
        ans.append(x)

print(*ans, sep='\n')

### FIXED CODE ###

N,Q = map(int,input().split())
STX = [tuple(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

starts = []
ends = []
for i,(s,t,x) in enumerate(STX):
    starts.append((s-x,i))
    ends.append((t-x,i))
starts.sort(key=lambda x:x[0], reverse=True)
ends.sort(key=lambda x:x[0], reverse=True)

import heapq
hq = []
heapq.heapify(hq)
delset = set()

ans = []
for d in D:
    while starts and starts[-1][0] <= d:
        _,i = starts.pop()
        x = STX[i][2]
        heapq.heappush(hq, x*N+i)
    while ends and ends[-1][0] <= d:
        _,i = ends.pop()
        delset.add(i)
    while hq:
        i = hq[0]%N
        if i in delset:
            heapq.heappop(hq)
        else:
            break
    if len(hq)==0:
        ans.append(-1)
    else:
        ans.append(hq[0]//N)

print(*ans, sep='\n')
### BUGGY CODE ###

class Tree:
    def __init__(self):
        self.nodes = {}
        self.roots = []

    def add(self, node):
        for i_number in self.roots:
            if i_number in node.degree:
                node.t = "root"
                r = self.nodes[i_number]
                if 0 < len(r.degree):
                    r.t = 'internal node'
                else:
                    r.t = 'leaf'
                r.parent = node.i
                self.roots.remove(i_number)
                self.roots.append(node.i)

        if len(self.nodes) == 0:
            node.t = 'root'
            self.roots.append(node.i)
        elif node.t != 'leaf' and node.t != 'root':
            node.t = 'internal node'

        if node.t != "root":
            for k, n in self.nodes.items():
                if node.i in n.degree:
                    node.parent = n.i

        self.nodes[node.i] = node

    def set_parent(self):
        for n in self.nodes.values():
            for deg in n.degree:
                child = self.nodes[deg]
                child.parent = n.i

    def calc_depth(self):
        for n in self.nodes.values():
            if n.parent == -1:
                continue
            else:
                p = self.nodes[n.i]
                depth = 0
                while not (p.parent == -1):
                    p = self.nodes[p.parent]
                    depth += 1
                n.depth = depth


class Node:
    def __init__(self, i=-1, parent=-1, depth=0, t="n", degree=[]):
        self.i = i
        self.parent = parent
        self.depth = depth
        self.t = t
        self.degree = degree
        if 0 < len(self.degree):
            self.leaf = False
        else:
            self.leaf = True
            self.t = "leaf"

    def show(self):
        ans = 'node {}: parent = {}, depth = {}, {}, {}'.format(self.i, self.parent, self.depth, self.t, self.degree)
        print(ans)

n = int(input())
tree = Tree()
for i in range(n):
    A = list(map(int, input().split()))
    node = Node(i=A[0], degree=A[2:])
    tree.add(node)

tree.set_parent()
tree.calc_depth()

for k, node in tree.nodes.items():
    node.show()

### FIXED CODE ###

def set_info(i, p, d):
    r = T[i]
    r[1], r[2] = p, d
    for c in r[0]:
        set_info(c, i, d+1)

n = int(input())
T = [None] * n
root = set(range(n))

for i in range(n):
    A = list(map(int, input().split()))
    ch = A[2:]
    T[A[0]] = [ch, None, None]
    root -= set(ch)

set_info(root.pop(), -1, 0)

for i,node in enumerate(T):
    ch, p, d = node
    print('node {}: parent = {}, depth = {}, {}, {}'.format(
            i, p, d, 'root' if not d else 'internal node' if ch else 'leaf', ch
        ))
### BUGGY CODE ###

N = int(input())
a_lis = list(input().split())

# 10^18を超えたら駄目

ans=1

for j in a_lis:
    ans=ans*int(j)

if ans>pow(10,18):
    print("-1")
else:
    print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

num=int(input())
a=list (map(int,input().split()))
count=0
while  all(i%2==0 for i in a):
  for i in a:
    i/2
    count+=1
print(count)


### FIXED CODE ###

num=int(input())
a=list (map(int,input().split()))
count=0
while  all(i%2==0 for i in a):
  a=[i/2 for i in a]
  count+=1
print(count)
### BUGGY CODE ###

n = int(input())
p_list = [int(input()) for _ in range(n)]

q_dict = {0:0}
for p in p_list:
    q_dict[p] = p_list.index(p)
length = 0
ans = 1
for i in range(1, n+1):
    if q_dict[i] > q_dict[i-1]:
        length += 1
        if length > ans:
            ans = length
    else:
        length = 1
print(n - ans)


### FIXED CODE ###

n = int(input())
p_list = [int(input()) for _ in range(n)]

q_dict = {0:0}
for i in range(n):
    q_dict[p_list[i]] = i
length = 0
ans = 1
for i in range(1, n+1):
    if q_dict[i] > q_dict[i-1]:
        length += 1
        if length > ans:
            ans = length
    else:
        length = 1
print(n - ans)
### BUGGY CODE ###

def resolve():
    N, K = list(map(int, input().split()))
    if (K == 1):
        print(0)
        return
    if N % K == 0:
        print(0)
        return
    x = N
    memo = [N]
    while True:
        x = min(abs(x - K), x)
        if x in memo:
            print(min(memo))
            return
        memo.append(x)
    return


resolve()


### FIXED CODE ###

def resolve():
    N, K = list(map(int, input().split()))
    print(min(N % K, K - (N % K)))
    return


resolve()
### BUGGY CODE ###

l = input().rstrip()
n = len(l)
total = 0

mod = 10**9 + 7
c = 1
for i in range(n):
    if l[i] == '1':
        total += c * pow(3, n-i-1, mod)
        total %= mod
        c <<= 1
total += c
total %= mod
print(total)

### FIXED CODE ###

l = input().rstrip()
n = len(l)

mod = 10**9 + 7
c = 1
d = 0
for i in range(n):
    d *= 3
    if l[i] == '1':
        d += c
        c <<= 1
    d %= mod
    c %= mod

print((c+d)%mod)
### BUGGY CODE ###

x = int(input())
a = list(map(int, input().split()))
al = [0]*x
for i in range(x):
    for j in range(x):
        abst = abs(i - a[j])
        if abst == 1 or abst == 0:
            al[i] += 1

print(max(1, max(al)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
al = [0]*(10**5+2)

for i in a:
    al[i] += 1
    al[i+1] += 1
    al[i+2] += 1

print(max(al))
### BUGGY CODE ###

#import numpy as np
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for i in range(N)]
seen = [0]*N
for val in AB:
    x, y = val
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
#print(dijkstra_heap(0))

lenedge = [len(val) for val in edge]
mledge = max(lenedge)
root = lenedge.index(mledge)
print(mledge)

colors = [[0]*N for _ in range(N)]
color_list = list(range(1, mledge+1))

que = deque()
que.append([(root, -1)])
while que[0]:
    nque = []
    cque = que.popleft()
    #print('cstack:', cstack)
    for tupl in cque:
        index, pcolor = tupl
        seen[index] = 1
        color = 1
        if (color == pcolor): color += 1
        for edgei in edge[index]:
            if seen[edgei] == 0:
                nque.append((edgei, color))
                colors[edgei][index] = color
                colors[index][edgei] = color
                color += 1
                if (color == pcolor): color += 1
    que.append(nque)

#pri(color)

for ab in AB:
    a, b = ab
    print(colors[a-1][b-1])



### FIXED CODE ###

#import numpy as np
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
#AB = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for i in range(N)]
seen = [0]*N
colors = [0]*(N-1)
#for val in AB:
for i in range(N-1):
    x, y = list(map(int, input().split()))
    edge[x-1].append((i, y-1))
    edge[y-1].append((i, x-1))

lenedge = [len(val) for val in edge]
mledge = max(lenedge)
root = lenedge.index(mledge)
print(mledge)


que = deque()
que.append([(root, -1)])
while que[0]:
    nque = []
    cque = que.popleft()
    #print('cstack:', cstack)
    for tupl in cque:
        index, pcolor = tupl
        seen[index] = 1
        color = 1
        if (color == pcolor): color += 1
        for tupl2 in edge[index]:
            findex, edgei = tupl2
            if seen[edgei] == 0:
                nque.append((edgei, color))
                colors[findex] = color
                color += 1
                if (color == pcolor): color += 1
    que.append(nque)

#pri(color)

for color in colors:
    print(color)
### BUGGY CODE ###

import heapq
def SME():
    A = []
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.98
    count = 0
    ANS = [heapq.heappush(A,[x,i]) for i,x in enumerate(Whole)]
    for j in range(N) :
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    D.add(idx)
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
 
n,m = map(int,input().split())
 
a_list=[]
for i in range(m):
    a_list.append(int(input()))
 
def count(now,s,e):
    if now > e:
        return 0
    if now == e:
        return 1
    cnt=0
    cnt+=count(now+1,s,e)
    cnt+=count(now+2,s,e)
    return cnt
 
 
c_mod=1000000007
start=0
end=0
ans=1
before=100000
for a in a_list:
    if abs(before-a)==1:
        print(0)
        exit()
    # 各部分の移動方法
    end=a-1
    ans=ans*count(start,start,end)%c_mod
    start=a+1
    before=a
if end<n:
    end=n
    ans=ans*count(start,start,end)%c_mod
print(ans)

### FIXED CODE ###

c_mod=1000000007
n,m = map(int,input().split())

step=[0]*(n+1)
for _ in range(m):
    a=int(input())
    step[a-1]=-1

if step[0]!=-1:
    step[0]=1
if step[1]!=-1:
    step[1]=1
for i in range(n-1):
    if step[i]==-1:
        continue
    if step[i+1]!=-1:
        step[i+1]+=step[i]
    if step[i+2]!=-1:
        step[i+2]+=step[i]
print(step[n-1]%c_mod)