module Main where
import           Control.Monad
import           Data.Bits
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.Monoid
--import SegmentTree

data SegmentTree m = Empty | SegmentTree {node :: m,left :: SegmentTree m,right :: SegmentTree m,size :: Int} deriving (Show)

build :: Monoid m => Int -> SegmentTree m
build 0    = Empty
build n    = build' n 1

build' :: Monoid m => Int -> Int ->SegmentTree m
build' n sz 
    | sz<n   = build' n (2*sz)
    | otherwise = build'' sz

build'' :: Monoid m => Int -> SegmentTree m
build'' 0 = Empty
build'' 1 = SegmentTree mempty  Empty Empty 1
build'' sz = SegmentTree mempty subTree subTree sz
    where m = sz `div` 2
          subTree = build'' m



update :: Monoid m => SegmentTree m -> m -> Int -> SegmentTree m
update tree@(SegmentTree n l r size) value idx 
    | size == 1
    = SegmentTree value Empty Empty size
    | idx <= newSize
    = let newNode = node (update l value idx ) `mappend` node r
      in  SegmentTree newNode (update l value idx ) r size
    | otherwise
    = let newNode = node l
              `mappend` node (update r value (idx - newSize) ) 
      in  SegmentTree newNode l (update r value (idx - newSize) ) size
    where newSize = size `div` 2




query :: Monoid m => SegmentTree m -> Int -> Int -> m
query Empty _ _ =mempty 
query tree@(SegmentTree n l r sz) a b
    | a >= b  = mempty 
    | a == 0 && b == sz  =   n
    | b <= newSize   =   query l  a b
    | a >= newSize  =   query r  (a-newSize) (b-newSize)
    | otherwise     =   (query l  a newSize) `mappend` (query r  0 (b-newSize))
    where newSize = sz `div` 2

    
get :: Monoid m => SegmentTree m -> Int -> m
get tree idx = query tree idx (idx + 1)

initial :: Monoid m => [m] -> SegmentTree m
initial list = init' list 1

init' :: Monoid m =>  [m] -> Int -> SegmentTree m
init' [] idx = build (idx-1)
init' (m:ms) idx = update (init' ms (idx+1)) m idx


newtype Gcd = Gcd Integer deriving (Show,Eq,Ord,Read)

--instance Semigroup Gcd where
--    Gcd x <> Gcd y = Gcd (gcd x y)
instance Monoid Gcd where
    mempty = Gcd 0
    Gcd x `mappend` Gcd y = Gcd (gcd x y)

toI :: Gcd -> Integer
toI (Gcd x) = x

tuplify2 (x:y:_) = (x,y)
tuplify2 _ = undefined


readInt = fst . fromJust . BS.readInteger
readIntTuple = tuplify2 . map readInt . BS.words
readIntList = map readInt . BS.words

getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntNList n = map readIntList <$> replicateM (fromIntegral n) BS.getLine
getIntMatrix = map readIntList . BS.lines <$> BS.getContents
getIntTuple = readIntTuple <$> BS.getLine
getIntNTuples n = map readIntTuple <$> replicateM (fromIntegral n) BS.getLine
getIntTuples = map readIntTuple . BS.lines <$> BS.getContents

solve :: [Integer] -> Integer
solve a =
    let seg = initial (map Gcd a) :: SegmentTree Gcd
    in maximum $ map toI [(query seg 0 i) `mappend` (query seg (i+1) (length a)) | i <- [0..length a ]]

main :: IO ()
main = do 
    getLine
    a <- getIntList
--    let a = [6,15,18]
--    let a' = map Gcd a
--    let seg = initial a' :: SegmentTree Gcd
--    let seg' = build 3 :: SegmentTree Gcd
    print (solve a)
--    print $ [((query seg 0 i), (query seg (i+1) (length a))) | i <- [0..length a ]]
--    print seg
    return()

Measured memory_bytes: 49532