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

from collections import deque, defaultdict
n, q = map(int ,input().split())
c = list(map(int, input().split()))
data = []
for i in range(q):
    data.append([i] + list(map(int, input().split())))
data.sort(key=lambda x : x[1])
ans = [0 for i in range(q)]
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0 
num = 2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
good_ball = dict()
pre_r = 0
for i in range(q):
    index, l, r = data[i]
    l, r = l-1, r-1
    for j in range(pre_r, r+1):
        if c[j] in good_ball : 
            update(good_ball[c[j]], 0)           
        update(j, 1)
        good_ball[c[j]] = j
    ans[index] = query(l,r+1)
for i in range(q):
    print(ans[i])

### FIXED CODE ###

from sys import stdin
input = stdin.readline
n, q = map(int ,input().split())
c = list(map(int, input().split()))
data = []
for i in range(q):
    data.append([i] + list(map(int, input().split())))
data.sort(key=lambda x : x[2])
ans = [0 for i in range(q)]
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0 
num = 2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
good_ball = dict()
pre_r = 0
count = 0
for i in range(q):
    index, l, r = data[i]
    l, r = l-1, r-1
    for j in range(pre_r, r+1):
        if c[j] in good_ball: 
            update(good_ball[c[j]], 0)           
        update(j, 1)
        good_ball[c[j]] = j
    pre_r = r + 1
    ans[index] = query(l, r+1)
for i in range(q):
    print(ans[i])
### BUGGY CODE ###

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

max_digit = 40

# xのn桁目が1かどうか
def JudgeDigitN(x, n):
    return x & 2**n == 2**n 
    
c1 = [0] * max_digit
for i in a:
    for j in range(max_digit):
        if JudgeDigitN(i,j):
            c1[j] += 1
b = []

for i in range(max_digit-1,-1,-1):
    if not JudgeDigitN(k,i):
        continue
    tmp = 0
    for j in range(max_digit-1,i,-1):
        if JudgeDigitN(k,j):
            tmp += 2**j * (n-c1[j])
        else:
            tmp += 2**j * c1[j]
    tmp += 2**i * c1[i]
    for j in range(i-1, -1, -1):
        tmp += 2**j * max(c1[j], n-c1[j])
    b.append(tmp)
    
tmp = 0    
for i in range(max_digit):
    if JudgeDigitN(k,i):
        tmp += 2**i * (n-c1[i])
    else:
        tmp += 2**i * c1[i]
b.append(tmp)

print(max(b))

### FIXED CODE ###

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

keta = 0
kc = k
while kc != 0:
    kc = kc//2
    keta += 1

i = keta-1
num = 0
res = 0

while i != -1:
    num *= 2
    count0 = 0
    count1 = 0
    for j in a:
        if j & pow(2, i) == 0:
            count0 += 1
        else:
            count1 += 1
    if count0 >= count1 and k >> i >= num+1:
        num += 1
    i -= 1
    
for i in a:
    res += num ^ i
    
print(res)
### BUGGY CODE ###

import bisect
N=int(input())
A=sorted(map(int,input().split()))
B=sorted(map(int,input().split()))
C=sorted(map(int,input().split()))
x=[1 for _ in range(N)]
for i in range(N):
        x[i]=N-bisect.bisect_right(C,B[i]) #B[i]より大きい要素の番号の数

ans=0
for i in range(N):
        j=bisect.bisect_right(B,A[i])
        ans+=sum(x[j:N])

print(ans)

### FIXED CODE ###

import bisect
N=int(input())
A=sorted(map(int,input().split()))
B=sorted(map(int,input().split()))
C=sorted(map(int,input().split()))
x=[1 for _ in range(N)]
ans=0
for i in range(N):
        a=bisect.bisect_left(A,B[i]) 
        c=N-bisect.bisect_right(C,B[i])
        ans+=a*c
print(ans)
### BUGGY CODE ###

K,S = map(int,input().split())


count = 0
for i in range(K+1):
  for j in range(K+1):
    left = S-(i+j)
    low = 0
    high = K

    while low <= high:
      n = (low + high) // 2
      if left == n:
        count += 1
        break
      elif left < n:
        high = n - 1
      elif left > n:
        low = n + 1

print(count)

### FIXED CODE ###

k,s = map(int,input().split())
count = 0
for i in range(k+1):
    for j in range(k+1):
        if 0 <= s-(i+j) <=k:
            count += 1
print(count)
### BUGGY CODE ###

import sys
for line in sys.stdin:
    n=int(line)
    plist = [1 for i in xrange(n+1)]
    plist[0]=0
    plist[1]=0
    i=2
    while True:
        pos0 = 2*i
        if pos0 < len(plist):
            plist[pos0] = 0
        else:
            break
        i+=1
    if n>7:
        for x in xrange(3,int(n**0.5)+1):
            if plist[x] == 1:
                i=3
                while True:
                    pos0 = x*i
                    if pos0 < len(plist):
                        plist[pos0] = 0
                    else:
                        break
                    i+=2
    print plist.count(1)

### FIXED CODE ###

#! -*- coding:utf-8 -*-
import sys
# import time
for line in sys.stdin:
  n=int(line)
  # n=input()
  # start = time.time()
  #plist = [1 for i in xrange(n+1)]
  #??¨??¨1???????????????
  #1?????¨???????????????????´???°??¨??????
  plist = [1]*(n+1)
  #0??¨1????´???°?????????????????§0???????????????
  plist[0]=plist[1]=0
  i=2
  #??¶??°????????????????????????
  while True:
      pos0 = 2*i
      if pos0 < len(plist):
          plist[pos0] = 0
      else:
          break
      i+=1
  #???????????¨????????????????????????
  for x in xrange(3,int(n**0.5)+1):
    if plist[x]:
      for pos0 in xrange(x**2,n+1,x):
        plist[pos0] = 0
  # elapsed_time = time.time()-start
  # print elapsed_time
  print plist.count(1)
### BUGGY CODE ###

M=998244353;n,A,B,K=map(int,input().split());F=[1]
for i in range(n):F+=[F[-1]*(i+1)%M]
C=lambda k:F[n]*pow(F[k]*F[n-k],M-2,M)if 0<=k<=n else 0;a=0
for i in range(n+1):
 r=K-i*A
 if r%B==0:a+=C(i)*C(r//B);a%=M
print(a)

### FIXED CODE ###

U = 3*10**5
MOD = 998244353
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
n, a, b, k = map(int, input().split())
ans = 0
for i in range(n+1):
  r = k - i*a
  if r%b==0 and 0 <= r//b <= n:
    ans += comb(n, i) * comb(n, r//b)
    ans %= MOD
print(ans)
### BUGGY CODE ###

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

data=[[0]*(s+1) for i in range(n)]

gen=data[0]
gen[0]=2
if(a[0]<=s):
    gen[a[0]]+=1

for i in range(1,n):
    gen=data[i]
    mae=data[i-1]
    for j in range(s+1):
        gen[j]=mae[j]*2
        if(j-a[i]>=0 and j-a[i]<=s):
            gen[j]+=mae[j-a[i]]
        gen[j]%=p

print(data[-1][-1])

### FIXED CODE ###

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

data=[[0]*(s+1) for i in range(n)]

gen=data[0]
gen[0]=2
if(a[0]<=s):
    gen[a[0]]+=1

for i in range(1,n):
    gen=data[i]
    mae=data[i-1]
    for j in range(s+1):
        gen[j]=mae[j]*2
        if(j-a[i]>=0 and j-a[i]<=s):
            gen[j]+=mae[j-a[i]]
        gen[j]%=p

print(data[-1][-1])
### BUGGY CODE ###

h, n = map(int, input().split())
dp = [1000000000] * (h+1)
dp[0] = 0
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h):
        # nj = min(j + a, h)
        if j + a < h: nj = j + a
        else: nj = h
        # dp[nj] = min(dp[nj], dp[j] + b)
        if dp[nj] < dp[j] + b: dp[nj] = dp[nj]
        else: dp[nj] = dp[j] + b
print(dp[h])

### FIXED CODE ###

h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
###一次元DP
dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        temp = i - a
        if temp < 0:
            temp = 0
        need_magic = dp[temp] + b
        if need_magic < dp[i]:
            dp[i] = need_magic
        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print(dp[-1])
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        for i in range(0, 10**6+1):
            if p % (2**(i+1)) != 0:
                ans *= 2**(i//n)
                p //= 2**i
                break
        for i in range(3, 10**6+1, 2):
            if i**n > p:
                break
            for j in range(0, 10**6+1):
                if p % (i**(j+1)) != 0:
                    ans *= i**(j//n)
                    p //= i**j
                    break
        print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from math import log
def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        if n > int(log(p, 2))+2:
            print("1")
            sys.exit()
        if p % (2**n) == 0:
            while p % (2**n) == 0:
                ans *= 2
                p //= (2**n)
        for i in range(3, 10**6+1, 2):
            while p % (i**n) == 0:
                ans *= i
                p //= (i**n)
        print(ans)

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

from functools import reduce
import operator
import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if not ANS[idx]:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if not ANS[i] : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if not ANS[i] : 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()]
parameter = 0.9906
INIT = None
ANS = [INIT]*N
ANS = SME(0, N)
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 ###

n=int(input())
a=list(map(int,input().split()))
list1=[]
ans=0
for i in range(n):
  ans+=(a[i]*sum(a[i+1:n]))%(10**9+7)
print(ans%(10**9+7))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
suma=sum(a)
for i in range(n):
  suma-=a[i]
  ans+=(a[i]*(suma))%(10**9+7)
print(int(ans%(10**9+7)))
### BUGGY CODE ###

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

def divisor(N):
    from math import sqrt
    D = []
    for i in range(1, int(sqrt(N)) + 1):
        if N % i == 0:
          D.append(i)
          D.append(N // i)

    return list(set(D))


count = 0
A_set = set(A)
A_dict = {a: 0 for a in A}
for a in A:
    A_dict[a] += 1
    
for a in A:
    a_div = set(divisor(a)) - {a}
    if len(a_div - A_set) == len(a_div):
        if A_dict[a] == 1:
            count += 1

print(count)

### FIXED CODE ###

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

A_max = max(A)
dp = [True] * (A_max + 1)
count = 0
A_f = {a: 0 for a in A}
for a in A:
    A_f[a] += 1

for a in A:
    if dp[a]:
        for i in range(1, A_max + 1):
            if a * i > A_max:
                break
            dp[a * i] = False
        if A_f[a] == 1:
            count += 1

print(count)
### BUGGY CODE ###

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

for i in range(1, n + 1):
    print(a.count(i))

### FIXED CODE ###

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

ans = [0]*n
for i in a:
    ans[i - 1] += 1

for j in ans:
    print(j)
### BUGGY CODE ###

from itertools import chain
import sys
sys.setrecursionlimit(99999)

s = input().rstrip()

def f(s):
    l = s.split('01')
    for i in range(len(l)):
        l[i] = l[i].split('10')
    l = list(chain.from_iterable(l))
    if len(l) == 1:
        return 0
    else:
        r = (len(l) - 1) * 2
        return r + f(''.join(l))

print(f(s))


### FIXED CODE ###

s = input().rstrip()

print(2 * min(s.count('0'), s.count('1')))
### BUGGY CODE ###

import collections
N, K = map(int, input().split())
G = [set() for i in range(N)]

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

q = collections.deque()
q.append((0))
ans = K
mod = 10**9+7
r = [True]*N
r[0] = False
while(q):
    x = q.popleft()
    tmp = K - 1
    if x > 0:
        tmp -= 1
    for y in G[x]:
        if r[y]:
            r[y] = False
            q.append(y)
            ans *= tmp
            tmp -= 1
    ans %= mod
print(ans)


### FIXED CODE ###

import collections
N,K=map(int,input().split())
G=[set() for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  G[a].add(b)
  G[b].add(a)
m=0
id=9
for i in range(N):
  if len(G[i])>m:
    id=i
    m = len(G[i])
q=collections.deque()
q.append(0)
colored=[False]*N
colored[0]=True
from math import factorial
mod = 10**9 + 7
ans = K
while(q):
  x= q.popleft()
  count=0
  for y in G[x]:
    if colored[y]:
      continue
    else:
      q.append(y)
      colored[y]=True
      count+=1
      
  for i in range(count):
    ans *= K-1-(len(G[x])-count)-i
    ans %= mod
  #print(ans,count,factorial(K-1-(len(G[x])-count)),factorial(count))
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split(' ')))
d = {}
for i in range(1, n+1):
    d[i] = a[i-1]

sorted = sorted(d.items(), key=lambda x: x[1])

ans = ''
for k, v in sorted:
    ans += str(k) + ' '
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(' ')))
ans = [0] * n
for i in range(n):
    h = a[i] - 1
    ans[h] = i + 1
print(' '.join(map(str, ans)))
### BUGGY CODE ###

a,b,k=map(int,input().split())
l=[]
for i in range(a,b+1):
	if min(i-a,b-i)<k:
		l.append(i)
print(*l,sep='\n')

### FIXED CODE ###

a,b,k=map(int,input().split())
aa=set(range(a,min(b+1,a+k)))
bb=set(range(max(b-k+1,a),b+1))
print(*sorted(aa|bb),sep='\n')
### BUGGY CODE ###

n = int(input())
p = [int(s) for s in input().split()]
count = 0
for a in range(n):
     i = p[a]
     num = -1
     C = 0
     while num != a:
         num+=1
         if p[num]<i:
             C+=1
     if C == 0:
         count+=1
print(count)

### FIXED CODE ###

n = int(input())
p = [int(s) for s in input().split()]
count = 0
M = p[0]
for a in range(n):
     i = p[a]
     if M >=i :
          count+=1
          M = i
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())

a=[0]*(n+1)
for i in range(1,n+1):
    for j in range(1,42):
        for k in range(1,42):
            for l in range(1,42):
                if j**2+k**2+l**2+j*k+k*l+l*j==i:
                    a[i]+=1

for x in range(1,n+1):
    print(a[x])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())

a=[0]*(n)
for j in range(1,n+1):
    for k in range(1,n+1):
        for l in range(1,n+1):
            if j**2+k**2+l**2+j*k+k*l+l*j>n:
                break
            else:
                a[j**2+k**2+l**2+j*k+k*l+l*j-1]+=1

for i in a:
    print(i)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0
for i in range(n):
    if min(p[:i+1]) == p[i]:
        ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0
pmin = 10**7
for i in range(n):
    pmin = min(pmin,p[i])
    if p[i] <= pmin:
        ans+=1
print(ans)
### BUGGY CODE ###

l,r = map(int,input().split())
r = min(r,l+4038)
mod = 0
ans = 2018

for i in range(l,r+1):
    for j in range(i+1,r+1):
        mod = i*j%2019
        ans = min(mod,ans)
        
print(ans)

### FIXED CODE ###

l,r = map(int,input().split())
r = min(r,l+678)
ans = 2018

for i in range(l,r+1):
    for j in range(i+1,r+1):
        ans = min(i*j%2019,ans)
print(ans)
### BUGGY CODE ###

mod = 10 ** 9 + 7

SIZE = 2 * 10 ** 6 + 5
fact = [0] * SIZE
inv = [0] * SIZE
finv = [0] * SIZE
fact[0], fact[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1
for i in range(2, SIZE):
    fact[i] = fact[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def nCr(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    return fact[n] * (finv[r] * finv[n - r] % mod) % mod


k = int(input())
S = input()
s_length = len(S)
full_length = len(S) + k
ans = 0
for i in range(k+1):
    add = pow(26, i, mod) * pow(25, k-i, mod) * nCr(full_length-i-1, s_length-1) % mod
    ans = (ans + add) % mod

print(ans)


### FIXED CODE ###

mod = 10 ** 9 + 7

SIZE = 2 * 10 ** 6 + 5
fact = [0] * SIZE
inv = [0] * SIZE
finv = [0] * SIZE
fact[0], fact[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1
for i in range(2, SIZE):
    fact[i] = fact[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def nCr(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    return fact[n] * (finv[r] * finv[n - r] % mod) % mod


k = int(input())
S = input()
s_length = len(S)
full_length = len(S) + k
ans = 0
for i in range(k+1):
    add = pow(26, i, mod) * pow(25, k-i, mod) * nCr(full_length-i-1, s_length-1) % mod
    ans = (ans + add) % mod

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

import copy
import bisect

N = int(input())
A = map(int, input().split())
C = [0]*(N + 1)
for a in A:
    C[a] += 1
sorted_C = sorted(C)

def h(L, i):
    """
    sorted_C[N - i : N]の最小の所に、sorted_C[ : N - i]を順番に積み上げるイメージ
    """
    if i == 1:
        return N
    
    for j in range(N - i, 0, - 1):
        if L[j] == 0:
            return L[N - i + 1]
        
        L[N - i + 1] += L[j]
        a = bisect.bisect_right(L[N - i + 2: ], L[N - i + 1])
        L[N - i + 1:] = L[N - i + 2: N - i + 2 + a] + [L[N - i + 1]] + L[N - i + 2 + a :]
        # L[i -1]が大きくなったからソートし直す
        # これはL[0 : i - 2]はソート済みだからbisectでL[0 : i - 2]にL[i - 1]が入るいちを見つければ良い。下の解答参照
    return L[N - i + 1]
        
for i in range(N):
    L = copy.copy(sorted_C)
    print(h(L, i + 1))

### FIXED CODE ###

N = int(input())
A = map(int, input().split())
C = [0]*N
for a in A:
    C[a - 1] += 1
D = [0]*(N + 1)
for c in C:
    D[c] += 1

Dk_accum = [0]*(N + 1)
for i in range(1, N + 1):
    Dk_accum[i] = Dk_accum[i - 1] + i*D[i]
    
D_sum = sum(D)
D_accum = [0]*(N + 2)
D_accum[0] = D_sum
for i in range(1, N + 1):
    D_accum[i] = D_accum[i - 1] - D[i - 1]
    
F = [0]*(N + 1)
for i in range(1, N + 1):
    F[i] = (Dk_accum[i]//i + D_accum[i + 1])

i = N
for K in range(1, N + 1):
    while i > 0 and K > F[i]:
        i -= 1
    print(i)
### BUGGY CODE ###

N = int(input())
L = [int(s) for s in input().split(' ')]

while len(L) > 1:
  L.sort()
  if L[-1] % L[0] == 0:
    L.pop()
  else:
    L[-1] = L[-1] % L[0]
print(L[0])

### FIXED CODE ###

N = int(input())
L = [int(s) for s in input().split(' ')]

while len(L) > 1:
  L.sort()
  L_new = [L[0]]
  for l in L[1:]:
    v = l % L_new[0]
    if v != 0:
      L_new.append(v)
  L = L_new
print(L[0])
### BUGGY CODE ###

"""
問題文

N個の整数 A1,A2,...,ANが黒板に書かれています。
あなたはこの中から整数を 1つ選んで、1 以上 109以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。書き換えた後のN個の整数の最大公約数の最大値を求めてください。

制約
入力は全て整数である。
2≤N≤105
1≤Ai≤109
"""

"""
3 5 7
最大公約数: 1
最大の最大公約数: 1

8 4 6
最大公約数: 2
最大の最大公約数: 4
『aとbとcの最大公約数』　＝　『aとbの最大公約数』と『c』　の最大公約数

a B c
gcd1 = gcd(a , B)
gcd2 = gcd(B , c)

"""
import math
from fractions import gcd  # for Ver.3.4 or lower.
from functools import reduce

gcd_map = {}
def GCD(numbers):
    x = numbers[0]
    for i in range(len(numbers) - 1) : 
        x = gcd_sub(x , numbers[i + 1])
    return x

def gcd_sub(a , b) : 
    if (a , b) in gcd_map : return gcd_map[(a,b)]
    else : 
        rst = gcd(a , b)
        gcd_map[(a,b)] = rst
        return rst



def main() : 
    N = int(input())
    a_list = input().split(" ")
    a_list = [int(i) for i in a_list]
    maxValue = 0
    for i in range(N) : 
        if i == 0 : sub_a_list = a_list[1:]
        elif i == N - 1 : sub_a_list = a_list[:N-1]
        else : sub_a_list = a_list[0 : i ] + a_list[i + 1 :] 
        rst = GCD(sub_a_list)
        if maxValue < rst : maxValue = rst
    print(maxValue)
main()


### FIXED CODE ###

"""
問題文

N個の整数 A1,A2,...,ANが黒板に書かれています。
あなたはこの中から整数を 1つ選んで、1 以上 109以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。書き換えた後のN個の整数の最大公約数の最大値を求めてください。

制約
入力は全て整数である。
2≤N≤105
1≤Ai≤109
"""

"""
3 5 7
最大公約数: 1
最大の最大公約数: 1

8 4 6
最大公約数: 2
最大の最大公約数: 4
『aとbとcの最大公約数』　＝　『aとbの最大公約数』と『c』　の最大公約数

A1 , A2 , A3 ... An

gcd(A1 , A2 , A3 ... An-1) * N
= gcd * N * N
= gcd * N^2

gcd(A1 , A2 , A3 ... An-1)
gcd(A1 , A2 , A3 ... An-2 , An) = gcd(A1 , A2 , A3 ... An-2) , An
"""
def gcd(a, b):  # a>b
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

from functools import reduce
def GCD(numbers):
    if len(numbers) == 0 : return 0
    if len(numbers) == 1 : return numbers[0]
    if len(numbers) == 2 : 
        return gcd(numbers[0] , numbers[1])
    else : 
        value = GCD(numbers[:len(numbers)-1])
        result = gcd(value , numbers[len(numbers) - 1])
        return result

def main() : 
    N = int(input())
    a_list = input().split(" ")
    a_list = [int(i) for i in a_list]
    R = [0 for i in range(N - 1)]
    L = [0 for i in range(N - 1)]
    R[0] = a_list[0]
    L[0] = a_list[-1]

    for i in range(1 , N-1) : 
        R[i] = gcd(R[i - 1] , a_list[i])
    
    for j in range(1 , N-1) : 
        L[j] = gcd(L[j - 1] , a_list[- j - 1])
    
    maxValue = 0
    for i in range(N - 2) : 
        value = gcd(R[i] , L[N - i - 3])
        if value > maxValue : maxValue = value
    print(max(maxValue , R[-1] , L[-1]))
main()