C - GCD on Blackboard

C - GCD on Blackboard。
累積和を使ういい問題だが、難しい。

from fractions import gcd

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

left = [0]*n  
right = [0]*n

# 取り除く点を除いたGCDの累積
# 引き算できないので、両端から求めてそれぞれのgcdを取る
for i in range(n-1):  
    left[i+1] = gcd(left[i], A[i])
    right[n-i-2] = gcd(right[n-i-1], A[n-i-1])

ans = 0  
for i in range(n):  
    ans = max(ans, gcd(left[i], right[i]))
print(ans)

N**2分の計算量がかかる解法は比較的すぐに思いつく。