Harryxun/stf_run huggingface dataset:
def main():
    N, P = map(int, input().split())
    if N == 1:
        print(P)
        return
    primes = []
    i = 2
    while i**N <= P:
        isprime = True
        for p in primes:
            if i % p == 0:
                isprime = False
                break
        if isprime:
            primes.append(i)
        i += 1

    F = {}
    i = 0
    while P > 1 and i < len(primes):
        factor = primes[i]
        while P % factor == 0:
            if factor not in F:
                F[factor] = 0
            F[factor] += 1
            P //= factor
        i += 1
    retval = 1
    for p in F:
        if F[p] >= N:
            retval *= p
    print(retval)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, P = map(int, input().split())
    if N == 1:
        print(P)
        return
    if N >= 40:
        print(1)
        return

    i = 2
    retval = 1
    while P > 1 and i**N <= P:
        cnt = 0
        while P % i == 0:
            cnt += 1
            P //= i
        retval *= i ** (cnt // N)
        i += 1
    print(retval)


if __name__ == "__main__":
    main()
n=int(input())
mod = 1000000007
gp = []
gm = []
ga0  =0
gb0 = 0
ans = 1
cnt = 0
for _ in range(n):
    a,b= map(int,input().split())
    #a,b = 1,1
    if a == 0 and b == 0:
        cnt += 1
    elif  a == 0:
        ga0 += 1
    elif b == 0:
        gb0 += 1
    elif b/a > 0:
        gp.append(b/a)
    else:
        gm.append(b/a)
gp.sort()
gm.sort()

lp,lm=0,0
cntall = 0
while lp < len(gp) and lm < len(gm):
    cal = gp[lp]*gm[lm]
    if cal == -1:
        cntp,cntm = 1,1
        while lp +1 < len(gp) and  gp[lp] == gp[lp+1]:
            cntp += 1
            lp+=1
        while lm +1 < len(gp) and  gm[lm] == gm[lm+1]:
            cntm += 1
            lm+=1
        ans *= (pow(2,cntp,mod)+pow(2,cntm,mod))%mod-1
        ans %= mod
        lp+=1
        lm+=1
        cntall += cntp+cntm
    elif cal > -1:
        lp += 1
    else:
        lm += 1

ans *= (pow(2,ga0,mod)+pow(2,gb0,mod))%mod-1
ans %= mod
n -= ga0+gb0+cntall+cnt
ans *= pow(2,n,mod)
ans %= mod
ans += cnt - 1
ans %= mod
print(ans)

### FIXED CODE ###

from math import gcd

n=int(input())
mod=10**9+7

z = 0
za = 0
zb = 0
d = {}

for _ in range(n):
    a,b = map(int,input().split())
    if a == 0 and b ==0:
        z += 1
    elif a == 0:
        za += 1
    elif b == 0:
        zb += 1
    else:
        g = gcd(a,b)
        a //= g
        b //= g
        if a < 0:
            a, b = -a, -b
        if b > 0:
            if (a,b) in d:
                d[(a,b)][0] += 1
            else:
                d[(a,b)] = [1,0]
        else:
            if (-b,a) in d:
                d[(-b,a)][1] += 1
            else:
                d[(-b,a)] = [0,1]

ans = 1
for key in d:
    ans *= (pow(2,d[key][0],mod) + pow(2,d[key][1],mod) - 1) % mod
    ans %= mod
ans *= (pow(2,za,mod) + pow(2,zb,mod) - 1) % mod
ans %= mod
print((ans + z - 1)%mod)
N = map(str,input())
M = [M for M in N]
print(M.count("2")


### FIXED CODE ###

N = map(str,input())
M = [M for M in N]
print(M.count("2"))
C = input()
k = [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]
for i in range(len(k)):
  if C == k[i]:
    print(k[i+1])


### FIXED CODE ###

C = input()
k = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
for i in range(len(k)):
  if C == k[i]:
    print(k[i+1])
try:
    A=int(input())
    B=int(input())
except:
    A,B=[int(i) for i in input().split(" ")]
if A<=8 and B<=8:
    print("Yay!")
else:
    print(":(")


### FIXED CODE ###

A,B=[int(i) for i in input().split(" ")]
if A<=8 and B<=8:
    print("Yay!")
else:
    print(":(")
import math

def str2list(str):
	result = []
	for value in str.split(' '):
		result.append(int(value))
	return result

def distance1(n, x, y):
	result = 0
	for i in range(n):
		result += abs(x[i] - y[i])
		
	return result
	
def distance2(n, x, y):
	result = 0
	for i in range(n):
		result += (x[i] - y[i]) * (x[i] - y[i])
		
	return math.sqrt(result)
	
def distance3(n, x, y):
	result = 0
	for i in range(n):
		result += math.pow(abs(x[i] - y[i]), 3)
		
	return math.exp(math.log(result)/3)
	
def distanceInf(n, x, y):
	result = 0
	for i in range(n):
		new_result = abs(x[i] - y[i])
		result = new_result if new_result > result else result
		
	return result

n = int(input());
x = str2list(input())
y = str2list(input())

print('%.6f'%distance1(n, x, y))
print('%.6f'%distance2(n, x, y))
print('%.6f'%distance3(n, x, y))
print('%.6f'%distanceInf(n, x, y))
import math

def str2list(str):
	result = []
	for value in str.split(' '):
		result.append(int(value))
	return result

def distance1(n, x, y):
	result = 0
	for i in range(n):
		result += abs(x[i] - y[i])
		
	return result
	
def distance2(n, x, y):
	result = 0
	for i in range(n):
		result += (x[i] - y[i]) * (x[i] - y[i])
		
	return math.sqrt(result)
	
def distance3(n, x, y):
	result = 0
	for i in range(n):
		result += math.pow(abs(x[i] - y[i]), 3)
		
	return math.exp(math.log(result)/3)
	
def distanceInf(n, x, y):
	result = 0
	for i in range(n):
		new_result = abs(x[i] - y[i])
		result = new_result if new_result > result else result
		
	return result

n = int(input());
x = str2list(input())
y = str2list(input())

print('%.6f'%distance1(n, x, y))
print('%.6f'%distance2(n, x, y))
print('%.6f'%distance3(n, x, y))
print('%.6f'%distanceInf(n, x, y))

### FIXED CODE ###

import math

def str2list(str):
	result = []
	for value in str.split(' '):
		result.append(int(value))
	return result

def distance1(n, x, y):
	result = 0
	for i in range(n):
		result += abs(x[i] - y[i])
		
	return result
	
def distance2(n, x, y):
	result = 0
	for i in range(n):
		result += (x[i] - y[i]) * (x[i] - y[i])
		
	return math.sqrt(result) if result != 0 else 0
	
def distance3(n, x, y):
	result = 0
	for i in range(n):
		result += math.pow(abs(x[i] - y[i]), 3)
		
	return math.exp(math.log(result)/3) if result != 0 else 0
	
def distanceInf(n, x, y):
	result = 0
	for i in range(n):
		new_result = abs(x[i] - y[i])
		result = new_result if new_result > result else result
		
	return result

n = int(input());
x = str2list(input())
y = str2list(input())

print('%.6f'%distance1(n, x, y))
print('%.6f'%distance2(n, x, y))
print('%.6f'%distance3(n, x, y))
print('%.6f'%distanceInf(n, x, y))
s=input()
n=len(s)
def p(s):
  return s==s[::-1]
if p(s[:(n-1)//2]):
  if p(s[(n+1)//2:]):
    print('Yes')
    exit()
   else:
    print('No')
    exit()
print('No')

### FIXED CODE ###

s=input()
n=len(s)
def p(s):
  return s==s[::-1]
if p(s):
  if p(s[:(n-1)//2]):
    if p(s[(n+1)//2:]):
      print('Yes')
      exit()
    else:
      print('No')
      exit()
print('No')
a = list(map(int, input().split()))
#print(a)
b=[0]*a[1]
c=[0]*(a[1]+1)
b[0]=int(input())
c[0]=b[0]-0
for x in range(a[1]-1):
    b[x+1]=int(input())
    c[x+1]=b[x+1]-b[x]-1
c[-1]=a[0]-b[-1]
max = 0
min = a[0]+100
for x in c:
    if x>max:
        max=x
    if x<min:
        min=x
        
#print(c)
#print(max," ",min)
if min==0:
    print(0)
else:
    num=[0]*(max)
    for x in range(max):
        if x==0:
            num[0]=1
        elif x==1:
            num[1]=1
        else:
            num[x]=num[x-1]+num[x-2]
        #print("num[",x,"]=",num[x])
        
    answer=1
    try:
        for x in c:
            answer *=num[x-1]
            if answer==0:
                print(0)
                break
            else:
                answer%=1000000007
        print(answer)
    except:
        print(0)

### FIXED CODE ###

n,m = list(map(int, input().split()))
a=[]
a.append(-1)
for x in range(m):
  tmp=int(input())
  a.append(tmp)
a.append(n+1)
diff = []
for x in range(len(a)-1):
  diff.append(a[x+1]-a[x])
              
large = 0
small = 123456789012345
for x in diff:
  large=max(large,x)
  small=min(small,x)

num=[0,0,1]
for _ in range(large):
  num.append((num[-1]+num[-2])%1000000007)
    
answer=1
for x in diff:
  #print(x,num[x])
  answer *=num[x]
  answer%=1000000007
print(answer)
import math
N = int(input())
print(N*(N-1)/2)


### FIXED CODE ###

S = input()
T = input()

c = 0

for i in range(len(S)):
  if S[i] == T[i]:
    c +=1
print(c)
# 接続最大クラスタのサイズが答え？

N, M = [int(x) for x in input().split(' ')]

from collections import defaultdict
d = defaultdict(set)

for i in range(M):
    a, b = [int(x) for x in input().split(' ')]
    d[a].add(b)
    d[b].add(a)

def bfs(i, obs=set()):
    # set_obs = d[i] | {i}
    obs |= {i}
    for j in d[i]:
        if j not in obs:
            obs |= bfs(j, obs)
    return obs

print(max(len(bfs(i, set())) for i in range(1, N+1)))

### FIXED CODE ###

# 接続最大クラスタのサイズが答え？

N, M = [int(x) for x in input().split(' ')]

# from collections import defaultdict
# d = defaultdict(set)

# for i in range(M):
#     a, b = [int(x) for x in input().split(' ')]
#     d[a].add(b)
#     d[b].add(a)

class UF:
    def __init__(self):
        self.r = [-1] * N

    def root(self, i):
        r = self.r
        if r[i] < 0:
            return i
        else:
            r[i] = self.root(r[i])
            return r[i]

    def union(self, i, j):
        i -= 1
        j -= 1
        ri = self.root(i)
        rj = self.root(j)
        if ri == rj:
            return
        else:
            if not self.r[ri] < self.r[rj]:
                ri, rj = rj, ri
            self.r[ri] += self.r[rj]
            self.r[rj] = ri
            return

    def max_size(self):
        return -min(self.r)

uf = UF()
for i in range(M):
    uf.union(*[int(x) for x in input().split(' ')])
print(uf.max_size())
import math

A = int(input())
B = int(input())
H = int(input())
M = int(input())
c = 0

h = H * 30 + 0.5 * M
m = 6 * M
#hh = abs(h - m)
hh = h - m
mm = 360 - hh

if hh <= mm:
    c = hh
else:
    c = mm

c = math.radians(c)

C = A * A + B * B - 2 * A * B * math.cos(c)
print(math.sqrt(C))

### FIXED CODE ###

n = str(input())
N = n[-1]

if N == "3":
  print("bon")
elif N == "0" :
  print("pon")
elif N == "1" :
  print("pon")
elif N == "6":
  print("pon")
elif N == "8":
  print("pon")
else:
  print("hon")
import math 

A, B = [int(item) for item in input().split()]

def gdc(A, B):

    while A > 1:
        A, B = B, A % B
    return A

def chk_pn(num):

    flag = True
    if num  <= 3:
        pass

    else:    
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                flag = False
                break
    return flag


def mk_factor(num):

    max_divisor = int(math.sqrt(num))+1
    divisor = 2
    factor_list = [1]

    while divisor <= max_divisor:
        if num % divisor == 0:
            factor_list.append(divisor)
            num /= divisor
        else:
            divisor += 1
    
    return factor_list

GDC = gdc(A, B)
pn_factor = [i for i in mk_factor(GDC) if chk_pn(i) is True]
# print(pn_factor)
print(len(set(pn_factor)))

### FIXED CODE ###

# start 21:14
a, b = [int(item) for item in input().split()]

# 素因数リスト
import math
def factor(num):
    divisor_list = [1]
    divisor = 2
    max_prime = int(math.sqrt(num))
    while max_prime >= divisor:
        if num % divisor == 0:
            divisor_list.append(divisor)
            num //= divisor

        else:
            divisor += 1
    divisor_list.append(num)
    return divisor_list

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)

cd_list = set(factor(gcd(a, b)))

print(len(cd_list))
import numpy as np
N,K = list(map(int,input().split()))
A = input()
A = list(A)
A = list(map(int,A))
l = [0]
s = []

for i in range(N-1):
    if A[i] != A[i+1]:
        l.append(i+1)
        s.append(l[len(l)-1]-l[len(l)-2])
l.append(N)
s.append(l[len(l)-1]-l[len(l)-2])
a = 0
right = 0
left = 0
g = 0
su = 0
if A[0] == 0:
    for i in range(len(s)):
        su +=s[right]
        if right%2==0:
            g += 1
        if g<=K:
            a = max(a,su)
            right +=1
        else:
            while g>K:
              su -= s[left]
              if left%2==0:
                  g -=1
              left +=1
else:
    for i in range(len(s)):
        su +=s[right]
        if right%2==1:
            g += 1
        if g<=K:
            a = max(a,su)
            right +=1
        else:
            while g>K:
              su -= s[left]
              if left%2==1:
                  g -=1
              left +=1
print(a)

### FIXED CODE ###

N,K = list(map(int,input().split()))
A = input()
A = list(A)
A = list(map(int,A))
l = [0]
s = []

for i in range(N-1):
    if A[i] != A[i+1]:
        l.append(i+1)
        s.append(l[len(l)-1]-l[len(l)-2])
l.append(N)
s.append(l[len(l)-1]-l[len(l)-2])
a = 0
right = 0
left = 0
g = 0
su = 0
if A[0] == 0:
    for i in range(len(s)):
        su +=s[right]
        if right%2==0:
            g += 1
        right +=1
        if g<=K:
            a = max(a,su)
        else:
            while g>K:
              su -= s[left]
              if left%2==0:
                  g -=1
              left +=1
        a = max(a,su)
else:
    for i in range(len(s)):
        su +=s[right]
        if right%2==1:
            g += 1
        right +=1
        if g<=K:
            a = max(a,su)
        else:
            while g>K:
              su -= s[left]
              if left%2==1:
                  g -=1
              left +=1
        a = max(a,su)

print(a)
def c(x):
    if sb[x] + S <= k: return True
    else: return False


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

sa = []
sb = []

if a[0] <= k:
    sa.append(a[0])
    for i in range(1, n):
        if sa[i-1]+a[i] > k:
            break
        sa.append(sa[i-1]+a[i])

if b[0] <= k:
    sb.append(b[0])
    for j in range(1, m):
        if sb[j-1]+b[j] > k:
            break
        sb.append(sb[j-1]+b[j])

if len(sa) == 0:
    print(len(sb))
    sys.exit()

for i in range(len(sa))[::-1]:
    mb = 0
    lb = len(sb) - 1
    if len(sb) == 0 or sa[i] + sb[0] > k:
        print(len(sa))
        sys.exit()
    
    while lb - mb > 1:
        mid = (mb+lb)//2
        if c(mid):
            mb = mid
        else:
            lb = mid
    ans = max(ans, i+1+lb)

print(ans)

### FIXED CODE ###

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

sa = [0]
sb = [0]

for i in range(n):
    sa.append(sa[i]+a[i])

for i in range(m):
    sb.append(sb[i]+b[i])

ans = 0
j = m

#しゃくとり
for i in range(n+1):
    if sa[i] > k:
        break
    while sa[i]+sb[j] > k:
        j -= 1
    ans = max(ans, i+j)

print(ans)
n=int(input())
A=list(map(int,input().split()))
B=[0 for i in range(n)]
flag=0
for i in range(1,int(n**0.5)+1):
    for j in range(0,n,i):
        B[i-1] +=A[j]
C=[]
for i in range(int(n**0.5)+1):
    if B[i]%2==A[i] and B[i]%2==0:
        flag=1
    if B[i]%2==A[i] and B[i]%2!=0:
        C.append(i+1)
        flag=1

if flag:
    if len(C)==0:print(0);exit()
    print(1)
    print(*C)
else:print(-1)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
B=[0 for i in range(n+1)]
C=[]
cnt=0
for i in range(1,n+1)[::-1]:
    sum_B=sum(B[j] for j in range(i,n+1,i))
    if sum_B%2!=A[i-1]:
        B[i]=1
        C.append(i)
        cnt +=1
print(cnt)
print(*[i for i in C[::-1]])
n = int(input())
s = list(map(int, input().split()))
print("Four" if "Y" in s else "Three")

### FIXED CODE ###

n = int(input())
s = list(input().split())
print("Four" if "Y" in s else "Three")
def f(y, m):
	if y in range(1, 13) and m in range(1, 13):
      return "AMBIGUOUS"
    if m in range(1, 13):
      return "YYMM"
    if y in range(1, 13):
      return "MMYY"
    return "NA"
  
S = input()
y, m = int(S[:2]), int(S[2:])
print(f(y, m))
  

### FIXED CODE ###

def f(y, m):
	if y in range(1, 13) and m in range(1, 13):
		return "AMBIGUOUS"
	if m in range(1, 13):
		return "YYMM"
	if y in range(1, 13):
		return "MMYY"
	return "NA"
  
S = input()
y, m = int(S[:2]), int(S[2:])
print(f(y, m))
N = list(input())
N.append(0)
for i in range(len(N)-1):
  if N[i] in'ACGT':
    N[i] += 1
    N[i+1] = N[i]
  else:
    N[i] = 0
print(max(N))

### FIXED CODE ###

N = list(input())
dp = [0]*(len(N)+1)
for i in range(len(N)):
  if N[i] in'ACGT':
    dp[i] += 1
    dp[i+1] = dp[i]
  else:
    dp[i] = 0
print(max(dp))
N = int(input())
A =  []
l1 = input().split()
for i in l1:
    A.append(int(i))
B = []
l2 = input().split()
for i in l2:
    B.append(int(i))
if sum(A) < sum(B):
    print(-1)
else:
    z = 0
    ar1 = []
    ar2 = []
    for i in range(N):
        if A[i] < B[i] :
            ar1.append(B[i] - A[i])
        if A[i] > B[i]:
            ar2.append(A[i] - B[i])
    if len(ar1) == 0:
        print(0)
    else:
        s = sum(ar1)
        ar2.sort(reverse = True)
        temp = 0
        b = 0
        for  i in range(len(ar2)):
            temp += ar2[i]
            if temp >= s:
                b = i+1
                break
        print(len(ar1)+b)


### FIXED CODE ###

l1  = input().split(" ")
ar = []
for i in l1:
  ar.append(int(i))
d = {1:0,9:0,7:0,4:0}
for i in ar:
  for j in d:
    if  i == j:
      d[j] = 1
con = True
for  i in d:
  if d[i] == 0:
    con = False
    print("NO")
    break
if con:
  print("YES")
A, B = map(int, raw_input().split()
print (A + B) % 24


### FIXED CODE ###

A, B = map(int, raw_input().split())
print (A + B) % 24
s = input()
n = int(input())
for i in range(n):
    q = input().split()
    if q[0] == '1':
        if len(s) != 1:
            s_new = ''
            for i in range(len(s)):
                s_new += s[len(s)-1-i]
            s = s_new
        else:
            pass
    else:
        if q[1] == '1':
            s = q[2] + s
        else:
            s += q[2]
    print(s)
print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
n = int(input())
q_list = [input().split() for i in range(n)]
count = 1
for i in q_list:
    if i[0] == '1':
        count *= -1
    else:
        if i[1] == '1':
            if count == 1:
                s.appendleft(i[2])
            else:
                s.append(i[2])
        else:
            if count == 1:
                s.append(i[2])
            else:
                s.appendleft(i[2])
if count != 1:
    s.reverse()
print(*s, sep='')
a = int(input())
b = int(input())

if (a + b) % 2 != 0:
    print("IMPOSSIBLE")
else:
    if a < b:
        A = a
        B = b
    else:
        A = b
        B = a

    K = int(B - (B - A) / 2)
    print(str(K))


### FIXED CODE ###

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

if a < b:
    A = a
    B = b
else:
    A = b
    B = a

if (B - A) % 2 != 0:
	print("IMPOSSIBLE")
else: 
	K = int(B - (B - A) / 2)
	print(str(K))
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
if N % 2 == 0:
    for i in range(N//2+1,2):
        if A[i] == A[i+1]:
            continue
        else:
            print(0)
            exit(0)
else:
    if A[0] == 0:
        for i in range(1,N//2+2,2):
            if A[i] == A[i+1]:
                continue
            else:
                print(0)
                exit(0)
    else:
        print(0)
        exit(0)
print(2**(N//2)%(10**9+7))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
if N == 1:
    print(1)
    exit(0)

elif N % 2 == 0:
    for i in range(0,N//2+1,2):
        if A[i] == A[i+1]:
            continue
        else:
            print(0)
            exit(0)
else:
    for i in range(1,N//2+2,2):
        if A[i] == A[i+1]:
            continue
        else:
            print(0)
            exit(0)
print(2**(N//2)%(10**9+7))
n=int(input())
l = list(map(int,input().split()))
s = set(l)
sl = sorted(list(s))
if len(s)==1 and sl[0]==0:
  print("Yes")
elif n%3==0 and l.count(sl[1])==(2*n)//3 and l.count(sl[0])==n//3 and sl[0]==0:
  print("Yes")
elif n%3==0 and len(s)==3 and l.count(sl[0])==l.count(sl[1])==l.count(sl[2]):
  if sl[0]^sl[1]^sl[2]==0:
    print("Yes")
  else:
    print("No")
else:
  print("No")


### FIXED CODE ###

n=int(input())
l = list(map(int,input().split()))
s = set(l)
sl = sorted(list(s))
if len(s)==1 and sl[0]==0:
  print("Yes")
elif n%3==0 and len(s)==2 and l.count(sl[1])==2*n//3 and l.count(sl[0])==n//3 and sl[0]==0:
  print("Yes")
elif n%3==0 and len(s)==3 and l.count(sl[0])==l.count(sl[1])==l.count(sl[2]):
  if sl[0]^sl[1]^sl[2]==0:
    print("Yes")
  else:
    print("No")
else:
  print("No")
a = int(input())
b = int(input())

if(a >= -100 and b <= 100):
	l = [a+b,a-b,a*b]
	print(max(l))

### FIXED CODE ###

a,b = map(int, input().split())
print(max(a+b, a-b, a*b))
N = int(input())
GACHA=[input() for n in range(N)]
print(len(set(GACHA)))

### FIXED CODE ###

import itertools

N, M, Q = map(int, input().split())
ABCD = [[int(x) for x in input().split()] for i in range(Q)]

ans=0
for A in itertools.combinations_with_replacement([m for m in range(1,M+1)], N):
  ans2=0
  for (a,b,c,d) in ABCD:
    if A[b-1]-A[a-1]==c:
      ans2+=d
  ans=max(ans, ans2)
print(ans)
N = int(input())
A = [int(_) for _ in input().split()]  # if int(_) < 19]
N = len(A)
while True:
    flag = True
    B = [A[0]]
    for i in range(N - 1):
        if A[i] >= A[i + 1]:
            B += [A[i + 1]]
        else:
            flag = False
    A = B.copy()
    N = len(A)
    if flag:
        break

if N == 1:
    print(1)
    exit()


def is_possible(K):
    dp = [0] * 19
    for i in range(N - 1):
        if B[i] >= B[i + 1]:
            dp = dp[: B[i + 1]] + [0] * (19 - B[i + 1])
            flag = True
            for j in range(B[i + 1] - 1, -1, -1):
                if dp[j] < K - 1:
                    dp[j] += 1
                    flag = False
                    break
                else:
                    dp[j] = 0
            if flag:
                return False
    return True


def bis(x, y):
    if y == x + 1:
        return y
    elif is_possible((x + y) // 2):
        return bis(x, (x + y) // 2)
    else:
        return bis((x + y) // 2, y)


print(bis(0, N))


### FIXED CODE ###

import random
input()
A = [int(_) for _ in input().split()]
A = [A[0]] + [j for i, j in zip(A, A[1:]) if i >= j]
N = len(A)


def cut(array, index):
    if index < 1:
        return []
    if index <= array[0][0]:
        return [(index, array[0][1])]
    for _ in range(len(array)-1, 0, -1):
        if array[_ - 1][0] < index:
            return array[:_] + [(index, array[_][1])]


def is_possible(K):
    dp = [(A[0], 0)]
    for a in A[1:]:
        if a <= dp[-1][0]:
            dp = cut(dp, a)
        else:
            dp += [(a, 0)]
        is_added = False
        for j in range(len(dp) - 1, -1, -1):
            if dp[j][1] < K - 1:
                dp = cut(dp, dp[j][0] - 1) + [(dp[j][0], dp[j][1] + 1)]
                if dp[-1][0] < a:
                    dp += [(a, 0)]
                is_added = True
                break
        if not is_added:
            return False
    return True


def bis(x, y):
    if y == x + 1:
        return y
    elif is_possible((x + y) // 2):
        return bis(x, (x + y) // 2)
    else:
        return bis((x + y) // 2, y)


print(bis(0, N))