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

import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp.keys() and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp.keys():
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp:
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


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

s = input()
K = int(input())
seta = set()
for i in s:
    seta.add(i)
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        seta.add(s[i:j])
print(sorted(list(seta))[K-1])

### FIXED CODE ###

s = input()
K = int(input())
seta = set()
for i in range(len(s)):
    for j in range(1,6):
        seta.add(s[i:i+j])
lista = sorted(list(seta))
print(lista[K-1])
### BUGGY CODE ###

n,m=map(int,input().split())
for i in range(n,m+1):
    if m%i==0:
        ans=m//i
        break
print(ans)

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

n,m=map(int,input().split())
l=make_divisors(m)
for i in l:
    if n<=i:
        ans=m//i
        break
print(ans)
### BUGGY CODE ###

import sys


def count_prime(n):
    global count, pool
    if not pool:
        return count
    p = pool[0]
    while p <= n:
        pool = tuple(i for i in pool if i % pool[0])
        count += 1
        if not pool:
            break
        p = pool[0]
    return count


inset = list(map(int, sys.stdin))
max_in = max(inset)
pool, count = tuple(range(3, max_in + 1, 2)), 1 if max_in > 1 else 0
inset = [(n, i) for i, n in enumerate(inset)]
inset.sort()
outset = [(t[1], count_prime(t[0])) for t in inset]
outset.sort()

print('\n'.join(map(str, [t[1] for t in outset])))

### FIXED CODE ###

import sys

input_list = list(int(i) for i in sys.stdin)
max_n = min(1000000, max(input_list) + 1)

prime_list = list(i % 2 for i in range(max_n))
prime_list[1], prime_list[2] = 0, 1
i = 3
while i * i < max_n:
    if prime_list[i]:
        for j in range(i * 2, max_n, i):
            prime_list[j] = 0
    i += 2

for i in range(1, max_n):
    prime_list[i] += prime_list[i - 1]

inset = sorted((n, i) for i, n in enumerate(input_list))
outset = sorted((t[1], prime_list[t[0]]) for t in inset)
for t in outset:
    print(t[1])
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
K = 60

ans = 0
mod = 10 ** 9 + 7

for i in range(K):
    bit = sum(A >> i & 1)
    ans += pow(2, i, mod) * (bit * (N - bit))

print(ans % mod)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

K = len(bin(np.max(A))) - 2

ans = 0
mod = 10 ** 9 + 7
N %= mod

for i in range(K):
    bit = np.count_nonzero(A >> i & 1) % mod
    ans += 2 ** i * bit * (N - bit)
    ans %= mod
    
print(ans)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    dp = [[float("inf"), set([])]  for _ in range(2 ** m)]
    dp[0][0] = 0
    a_list = []
    c_list = []
    for i in range(m):
        a, b = map(int, input().split())
        a_list.append(a)
        c_list.append([int(i) for i in input().split()])

    for i in range(1, 2 ** m):
        for j in range(m):
            c = c_list[j]
            a = a_list[j]
            if (i & (1 << j) == 1 << j):
                if len(set(c) - dp[i - (1 << j)][1]) > 0:
                    if len(set(c) - dp[i][1]) > 0:
                        dp[i][0] = dp[i - (1 << j)][0] + a
                        dp[i][1] = dp[i - (1 << j)][1] | set(c)
                    else:
                        if dp[i][0] > dp[i - (1 << j)][0] + a:
                            dp[i][0] = dp[i - (1 << j)][0] + a
                        else:
                            continue
                elif len(dp[i - (1 << j)][1]) == n:
                    if len(dp[i][1]) == n:                    
                        dp[i][0] = min(dp[i - (1 << j)][0], dp[i][0])
                    elif len(set(c) | dp[i][1]) == n:
                        dp[i][1] = dp[i - (1 << j)][1] | set(c)
                        dp[i][0] = min(dp[i - (1 << j)][0], dp[i][0] + a)
    if len(dp[-1][1]) == n:
        print(dp[-1][0])
    else:
        print(-1)

main()

### FIXED CODE ###

n, m = map(int, input().split())
dp = [[float('inf')] * 2 ** n for _ in range(m + 1)]
dp[0][0] = 0
for i in range(1, m + 1):
    a, b = map(int, input().split())
    c = [int(i_) for i_ in input().split()]
    temp = 0
    for kk in c:
        temp += 1 << (kk - 1)
    for j in range(2 ** n):
        if j == 0:
            dp[i][temp | j] = a
        else:
            dp[i][temp | j] = min(dp[i - 1][j] + a, dp[i][temp | j])
        if (i > 1):
            dp[i][j] = min(dp[i - 1][j], dp[i][j])

if dp[-1][-1] < float("inf"):
    print(dp[-1][-1])
else:
    print(-1)
### BUGGY CODE ###

import random
import time
import copy
start = time.time()
D = int(input())
s = [[0 for j in range(26)] for i in range(D)]
c = list(map(int, input().split(" ")))
result = []
total = -10000000
for i in range(D):
    a = list(map(int, input().split(" ")))
    for j, k in enumerate(a):
        s[i][j] = int(k)
while(1):
    result_tmp = []
    total_tmp=0
    last = [0 for i in range(26)]
    for i in range(D):
        score = [0 for i in range(26)]

        for j in range(26):
            score[j] = s[i][j]
            for k in range(26):
                if j != k:
                    score[j] -= (i + 1 - last[k]) * c[k]
        score_sort = sorted(score, reverse=True)
        score_max = score_sort[0]

        tmp = []
        for j in range(26):
            if score_max >= 0 and score_max*0.95 <= score[j]:
                tmp.append(j)
            if score_max < 0 and score_max*1.05 <= score[j]:
                tmp.append(j)

        score_max = random.choice(tmp)

        result_tmp.append(score_max)
        last[score_max] = i + 1
        total_tmp += score[score_max]
    if total < total_tmp:
        total=total_tmp
        result = result_tmp.copy()
    end = time.time()
    if end - start > 1.9:
        break
for i in range(D):
    print(result[i]+1)


### FIXED CODE ###

# coding: utf-8
# Your code here!

D = int(input())
# with open("sample1.in") as f:

#c = [0 for i in range(26)]
s = [[0 for j in range(27)] for i in range(D)]
c = list(map(int, input().split(" ")))
result=[]
# for i in range(26):
#    c[i] = int(input())
for i in range(D):
    a = list(map(int, input().split(" ")))
    for j, k in enumerate(a):
        #print(i, j, k)
        s[i][j] = int(k)
    result.append(a.index(max(a))+1)
    #print(a.index(max(a)))

for i in range(D):
    # print(s.index(max(s[i])))
    print(result[i])
### BUGGY CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
dp = [0]*N
for j in range(1,N):
  dp[j] = dp[j-1]+abs(H[j]-H[j-1])
for i in range(0,N+1):
  for j in range(K+1):
    if i+j <= N-1:
      dp[i+j] = min(dp[i+j],dp[i]+abs(H[i+j]-H[i]))
print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
dp = [0]*N
for j in range(1,N):
  dp[j] = dp[j-1]+abs(H[j]-H[j-1])
for i in range(0,N+1):
  for j in range(K+1):
    if i+j <= N-1:
      dp[i+j] = min(dp[i+j],dp[i]+abs(H[i+j]-H[i]))
print(dp[N-1])
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]

for i in range(N):
    num = A[i]
    A[i] = 0
    print(max(A))
    A[i] = num


### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]

maximum = max(A)
count_max = A.count(maximum)
if count_max > 1:
    for i in range(N):
        print(maximum)
else:
    for i in range(N):
        if A[i] != maximum:
            print(maximum)
        else:
            num = A[i]
            A[i] = 0
            print(max(A))
            A[i] = num
### BUGGY CODE ###

def solve(field,H,W):
    space = [[0]*(W+1) for _ in xrange(H)]
    for x in xrange(W-1,-1,-1):
        for y in xrange(H):
            if field[y][x]==".":
                space[y][x] = space[y][x+1]+1 
    ans = 0
    for x in xrange(W):
        for y in (yy for yy in xrange(H) if field[y][x] == "."):
            for h in xrange(y+1,H+1):
                ans = max(ans, min(s[x] for s in space[y:h])*(h-y))
                if ans > (W-x)*(H-y):
                    return ans
    return ans

while True:
    H,W = map(int, raw_input().split(" "))
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    print solve(field,H,W)

### FIXED CODE ###

def re_push(stack,num):#re_push and return max
    count = 0
    pre = num
    ma = 0
    while True:
        count += 1
        cur = stack.pop()
        if cur <= num:
            ma = max(ma,(count-1) * pre)
            stack += [cur]
            stack += [num]*(count-1)
            break
        if cur < pre:
            ma = max(ma,(count-1) * pre)
            stack += [cur]*count
            count = 0
        pre = cur
    return ma
            
while True:
    H,W = map(int, raw_input().split(" "))
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    table = [[0]*(W+1) for _ in xrange(H)]
    for y in xrange(H-1,-1,-1):
        for x in (x for x in xrange(W-1,-1,-1) if field[y][x] != "*"):
            table[y][x] = table[y][x+1] + 1
    ma = 0
    for x in xrange(W):
        stack = [0,table[0][x]]
        for y in xrange(1,H):
            if table[y-1][x] > table[y][x]:
                ma = max(ma, re_push(stack,table[y][x]))
            stack.append(table[y][x])
        ma = max(ma, re_push(stack,0))
    print ma
### BUGGY CODE ###

N, X, Y = map(int, input().split())
Graph = [[] for _ in range(N)]
for i in range(N):
    if i < N - 1:
        Graph[i].append(i + 1)
        Graph[i + 1].append(i)
    if X == i:
        Graph[X - 1].append(Y - 1)
        Graph[Y - 1].append(X - 1)
# print(Graph)
ans = [0] * (N - 1)
from collections import deque, Counter

for i in range(N):
    dist = [-1] * N
    que = deque([i])
    dist[i] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in Graph[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
    # print(dist)
    dist_Counter = Counter(dist)
    for key, val in dist_Counter.items():
        if key != 0:
            ans[key - 1] += val

for a in ans:
    print(a // 2)


### FIXED CODE ###

N, X, Y = map(int, input().split())
Graph = [[] for _ in range(N)]
for i in range(N):
    if i < N - 1:
        Graph[i].append(i + 1)
        Graph[i + 1].append(i)
    if X == i:
        Graph[X - 1].append(Y - 1)
        Graph[Y - 1].append(X - 1)
# print(Graph)
ans = [0] * (N - 1)
from collections import deque, Counter

for i in range(N):
    dist = [-1] * N
    que = deque([i])
    dist[i] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in Graph[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
    # print(dist)
    dist_Counter = Counter(dist)
    for key, val in dist_Counter.items():
        if key != 0:
            ans[key - 1] += val

for a in ans:
    print(a // 2)
### BUGGY CODE ###

from collections import*
from itertools import*
import sys
input=sys.stdin.readline
n,c=map(int,input().split())
cost=[list(map(int,input().split()))for i in range(c)]
d=defaultdict(list)
for i in range(n):
    for j,v in enumerate(map(int,input().split())):
        d[(i+j+2)%3].append(v-1)
ans=[]
for cmb in permutations(range(c),3):
    ans.append(sum(sum(cost[i][cmb[dindex]]for i in d[dindex])for dindex in range(3)))
print(min(ans))

### FIXED CODE ###

from itertools import*
n,c=map(int,input().split())
cost=[list(map(int,input().split()))for i in range(c)]
d=[[0]*c for i in range(3)]
for i in range(n):
    for j,v in enumerate(map(int,input().split())):
        d[(i+j)%3][v-1]+=1
print(min(sum(cost[j][cmb[i]]*d[i][j]for j in range(c)for i in range(3))for cmb in permutations(range(c),3)))
### BUGGY CODE ###

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

h.sort()
ans = 10**9
for i in range(0, n-k+1):
   hmax = max(h[i:i+k])
   hmin = min(h[i:i+k])
   if (hmax - hmin < ans):
      ans = hmax - hmin

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
height = [int(input()) for _ in range(n)]

height.sort()

diff = [height[i+k-1] - h for i, h in enumerate(height) if i+k-1 < len(height)]
print(min(diff))
### BUGGY CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


def lcm(a, b):
    """
    aとbの最小公倍数を計算します。
    """
    return a // gcd(a, b) * b


def main():
    N = int(input())
    A = list(map(int, input().split()))

    l = A[0]
    for i in range(1, N):
        l = lcm(l, A[i])

    ans = 0
    for a in A:
        ans += l // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))

    l = A[0]
    for i in range(1, N):
        l = l * A[i] // gcd(l, A[i])

    print(sum([l // a for a in A]) % MOD)


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

def e_crested_ibis_vs_monster_in_place():
    H, N = [int(i) for i in input().split()]
    Monsters = [[int(i) for i in input().split()] for j in range(N)]

    # dp[i][j]: 最初の i 種類の魔法でモンスターに j ダメージ与える場合の消費魔力の最小値
    # としたとき、更新順序を工夫することで添字 i をなくせる
    dp = [0] + [float('inf')] * H
    for a, b in Monsters:
        for j in range(H + 1):
            nj = min(j + a, H)
            dp[nj] = min(dp[nj], dp[j] + b)
    return dp[H]

print(e_crested_ibis_vs_monster_in_place())

### FIXED CODE ###

def e_crested_ibis_vs_monster():
    H, N = [int(i) for i in input().split()]
    Damage, Cost = [], []
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        Damage.append(a)
        Cost.append(b)

    # dp[i][j]: 最初の i 種類の魔法でモンスターに j ダメージ与える場合の消費魔力の最小値
    dp = [[float('inf')] * (H + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H + 1):
            # i 番目の魔法を使わない場合
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            # i 番目の魔法を使う場合
            dp[i + 1][min(j + Damage[i], H)] = min(dp[i + 1][min(j + Damage[i], H)],
                                                   dp[i + 1][j] + Cost[i])
    return dp[N][H]

print(e_crested_ibis_vs_monster())
### BUGGY CODE ###

from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (i/N)(dp[i-1][j][k])+(j/N)(dp[i+1][j-1][k])+(k/N)(dp[i][j+1][k-1])+(N-i-j-k/N)(dp[i][j][k])+1
# dp[i][j][k] = (i(dp[i-1][j][k])+j(dp[i+1][j-1][k])+k(dp[i][j+1][k-1])+N)/(i+j+k)

@lru_cache(maxsize=None)
def h(i,j,k):
  try:
    return ((i*h(i-1,j  ,k  ) if i else 0)+
            (j*h(i+1,j-1,k  ) if j else 0)+
            (k*h(i  ,j+1,k-1) if k else 0)+
            N)/(i+j+k)
  except ZeroDivisionError:
    return 0

print(h(A,B,C))

### FIXED CODE ###

from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (i/N)(dp[i-1][j][k])+(j/N)(dp[i+1][j-1][k])+(k/N)(dp[i][j+1][k-1])+(N-i-j-k/N)(dp[i][j][k])+1
# dp[i][j][k] = (i(dp[i-1][j][k])+j(dp[i+1][j-1][k])+k(dp[i][j+1][k-1])+N)/(i+j+k)
dp = [[[None]*(C+1) for _ in range(B+C+1)] for _ in range(A+B+C+1)]
dp[0][0][0] = 0

for k in range(C+1):
  for j in range(B+C+1-k):
    for i in range(A+B+C+1-k-j):
      try:
        dp[i][j][k] =((i*dp[i-1][j][k] if i else 0)+
                      (j*dp[i+1][j-1][k] if j else 0)+
                      (k*dp[i][j+1][k-1] if k else 0)+
                      N)/(i+j+k)
      except ZeroDivisionError:
        pass

print(dp[A][B][C])
### BUGGY CODE ###

N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
A = [0]*(N+1)
A[0] = 1
if not(1 in a):
  A[1] = 1
for i in range(2,N+1):
    if i in a:
      A[i] = 0
    else:
      A[i] = A[i-2] + A[i-1]
    A[i] %=1000000007
print(A[N])


### FIXED CODE ###

N,M = map(int,input().split())
a = set(int(input()) for x in range(M))
A = [0]*(N+1)
mod = 1000000007
A[0] = 1
if not(1 in a):
  A[1] = 1
for i in range(2,N+1):
    if i in a:
      A[i] = 0
    else:
      A[i] = (A[i-2] + A[i-1]) % mod
print(A[N])
### BUGGY CODE ###

N, C = [int(_) for _ in input().split()]

MT = (20 ** 5 + 10)
memo_s = [0] * MT
memo_t = [0] * MT
for i in range(N):
    s, t, c = [int(_) for _ in input().split()]

    memo_s[s*2] += 1 << (c - 1)
    memo_t[t*2+1] += 1 << (c - 1)

ans = 0
cnt = 0
for i in range(1, MT):
    for c in range(C):
        if memo_s[i] & (1 << c) == 0: continue
        if memo_t[i] & (1 << c): continue  # 区間連続
        cnt += 1
    ans = max(ans, cnt)
    for c in range(C):
        if memo_s[i] & (1 << c) == 1: continue

        if memo_t[i] & (1 << c):
            cnt -= 1
print(ans)

### FIXED CODE ###

N, C = [int(_) for _ in input().split()]

MT = (10 ** 5 + 10)

memo = [[0] * C for _ in range(MT)]

stc = sorted([[int(_) for _ in input().split()] for _ in range(N)])
for s, t, c in stc:
    if memo[s][c - 1] < 0:
        memo[s][c - 1] = 0
    else:
        memo[s - 1][c - 1] += 1
    memo[t][c - 1] -= 1
ans = 0
cnt = 0
for i in range(MT):
    cnt += sum(memo[i])
    ans = max(ans,cnt)
print(ans)
### BUGGY CODE ###

n = int(input())
ls = list(map(int,input().split()))
a = min(ls)
b = max(ls)
c = len(ls)
s = 0
def sub(p,q):
    return p-q
ans = []
aaa = -float("inf")
for i in range(a,b+1):
    new = [i]*(c)
    ans = map(sub,ls,new)
    ans = list(map(str,ans))
    s = ans.count("-1") + ans.count("1") + ans.count("0")
    aaa = max(aaa,s)
print(aaa)


### FIXED CODE ###

n = int(input())
ls = list(map(int,input().split()))
di = [0]*(max(ls)+3)
for i in ls:
    di[i] += 1
    di[i+1] += 1
    di[i+2] += 1
print(max(di))
### BUGGY CODE ###

from collections import deque
import bisect
import math
N, M = map(int, input().split())

A = sorted([-int(_) for _ in input().split()])
deq = deque(A)

for m in range(M):
    div = deq.popleft()
    div = math.ceil(div / 2)
    tmp_lis = list(deq)
    #print(tmp_lis)
    bisect.insort(tmp_lis, div)
    deq = deque(tmp_lis)
print(-sum(deq))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [-int(_) for _ in input().split()]
heapq.heapify(A)

tmp = 0
for m in range(M):
    div = -heapq.heappop(A)
    div = div // 2
    heapq.heappush(A, -div)
print(-sum(A))
### BUGGY CODE ###

X=int(input())

list=[]
if X==1:
    list.append(1)
for i in range(1,X):
    for j in range(2,X):
        if i**j <= X:
                list.append(i**j)
print(max(list))

### FIXED CODE ###

X=int(input())

list=[]
if X==1:
    list.append(1)
for i in range(1,X):
    for j in range(2,X):
        if i**j <= X:
                list.append(i**j)
        else:
            break
print(max(list))
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))

    MOD = 10 ** 9 + 7

    dp0 = [[0] * 2005 for _ in range(2005)]
    dp1 = [[0] * 2005 for _ in range(2005)]

    dp0[0][0] = 1
    for i in range(N + 1):
        for j in range(M + 1):
            dp0[i + 1][j] += dp0[i][j]
            dp1[i][j] += dp0[i][j]
            dp1[i][j + 1] += dp1[i][j]
            if i < N and j < M and S[i] == T[j]:
                dp0[i + 1][j + 1] += dp1[i][j]
            dp0[i][j] %= MOD
            dp1[i][j] %= MOD

    ans = dp1[N][M]
    print (ans)
    return 

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))

    MOD = 10 ** 9 + 7

    dp0 = [[0] * 2005 for _ in range(2005)]
    dp1 = [[0] * 2005 for _ in range(2005)]

    dp0[0][0] = 1
    for i in range(N + 1):
        for j in range(M + 1):
            dp0[i + 1][j] += dp0[i][j]
            dp1[i][j] += dp0[i][j]
            dp1[i][j] %= MOD
            dp1[i][j + 1] += dp1[i][j]
            if i < N and j < M and S[i] == T[j]:
                dp0[i + 1][j + 1] += dp1[i][j]
            dp1[i][j] %= MOD
            dp0[i + 1][j] %= MOD
            dp1[i][j + 1] %= MOD
            dp0[i + 1][j + 1] %= MOD

    ans = dp1[N][M] % MOD
    print (ans)
    return 

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

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(n):
    ans.append(a[i])
    ans.reverse()
print(' '.join(map(str, ans)))

### FIXED CODE ###

n = int(input())
a = input().split()
ans=[]
if n%2==0:
    for i in range(n - 1, -1, -2):
        ans.append(a[i])
    for i in range(0, n, 2):
        ans.append(a[i])
else:
    for i in range(n - 1, -1, -2):
        ans.append(a[i])
    for i in range(1, n, 2):
        ans.append(a[i])
print(' '.join(ans))