Problem: There are N integers, A_1, A_2, ..., A_N, written on the blackboard.  You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), possibly the same as the integer originally written.  Find the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Submission attempts (in order):
from fractions import gcd

#     return a if b == 0 else GCD(b, a % b)


class SegTree():
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.data = [ele_id] * (2 * self.n - 1)
        self.ele_id = ele_id
        self.operation_func = operation_func

    def __getitem__(self, idx):
        return self.data[idx + self.n - 1]

    def init(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.operation_func(self.data[2 * i + 1],
                                               self.data[2 * i + 2])

    def update(self, idx, x):
        
        idx += self.n - 1
        self.data[idx] = x
        while idx > 0:
            idx = (idx - 1) // 2
            self.data[idx] = self.operation_func(self.data[2 * idx + 1],
                                                 self.data[2 * idx + 2])

    def query(self, a, b):
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        
        if r <= a or b <= l:
            
            return self.ele_id

        if a <= l and r <= b:
            
            return self.data[k]
        else:
            
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.operation_func(child_l, child_r)


n = int(input())
a = list(map(int, input().split()))
seg_gcd = SegTree(n, 0, gcd)
seg_gcd.init(a)

ans = seg_gcd.data[0]
for i in range(n):
    
    
    
    ans = max(ans, gcd(seg_gcd.query(0, i), seg_gcd.query(i + 1, n)))

print(ans)


from fractions import gcd
import sys
input = sys.stdin.readline

#     return a if b == 0 else GCD(b, a % b)


class SegTree():
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.data = [ele_id] * (2 * self.n - 1)
        self.ele_id = ele_id
        self.operation_func = operation_func

    def __getitem__(self, idx):
        return self.data[idx + self.n - 1]

    def init(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.operation_func(self.data[2 * i + 1],
                                               self.data[2 * i + 2])

    def update(self, idx, x):
        
        idx += self.n - 1
        self.data[idx] = x
        while idx > 0:
            idx = (idx - 1) // 2
            self.data[idx] = self.operation_func(self.data[2 * idx + 1],
                                                 self.data[2 * idx + 2])

    def query(self, a, b):
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        
        if r <= a or b <= l:
            
            return self.ele_id

        if a <= l and r <= b:
            
            return self.data[k]
        else:
            
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.operation_func(child_l, child_r)


n = int(input())
a = tuple(map(int, input().split()))
seg_gcd = SegTree(n, 0, gcd)
seg_gcd.init(a)

ans = seg_gcd.data[0]
for i in range(n):
    seg_gcd.update(i, 0)
    ans = max(ans, seg_gcd.data[0])
    seg_gcd.update(i, a[i])

print(ans)


from fractions import gcd

#     return a if b == 0 else GCD(b, a % b)


class SegTree():
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.data = [ele_id] * (2 * self.n - 1)
        self.ele_id = ele_id
        self.operation_func = operation_func

    def __getitem__(self, idx):
        return self.data[idx + self.n - 1]

    def init(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.operation_func(self.data[2 * i + 1],
                                               self.data[2 * i + 2])

    def update(self, idx, x):
        
        idx += self.n - 1
        self.data[idx] = x
        while idx > 0:
            idx = (idx - 1) // 2
            self.data[idx] = self.operation_func(self.data[2 * idx + 1],
                                                 self.data[2 * idx + 2])

    def query(self, a, b):
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        
        if r <= a or b <= l:
            
            return self.ele_id

        if a <= l and r <= b:
            
            return self.data[k]
        else:
            
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.operation_func(child_l, child_r)


n = int(input())
a = tuple(map(int, input().split()))
seg_gcd = SegTree(n, 0, gcd)
seg_gcd.init(a)

ans = seg_gcd.data[0]
for i in range(n):
    seg_gcd.update(i, 0)
    ans = max(ans, seg_gcd.data[0])
    seg_gcd.update(i, a[i])

print(ans)


from fractions import gcd

#     return a if b == 0 else GCD(b, a % b)


class SegTree():
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.data = [ele_id] * (2 * self.n - 1)
        self.ele_id = ele_id
        self.operation_func = operation_func

    def __getitem__(self, idx):
        return self.data[idx + self.n - 1]

    def init(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.operation_func(self.data[2 * i + 1],
                                               self.data[2 * i + 2])

    def update(self, idx, x):
        
        idx += self.n - 1
        self.data[idx] = x
        while idx > 0:
            idx = (idx - 1) // 2
            self.data[idx] = self.operation_func(self.data[2 * idx + 1],
                                                 self.data[2 * idx + 2])

    def query(self, a, b):
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        
        if r <= a or b <= l:
            
            return self.ele_id

        if a <= l and r <= b:
            
            return self.data[k]
        else:
            
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.operation_func(child_l, child_r)


n = int(input())
a = list(map(int, input().split()))
seg_gcd = SegTree(n, 0, gcd)
seg_gcd.init(a)

ans = seg_gcd.data[0]
for i in range(n):
    seg_gcd.update(i, 0)
    ans = max(ans, seg_gcd.data[0])
    seg_gcd.update(i, a[i])

print(ans)


def main():
    from fractions import gcd
    import sys
    input = sys.stdin.readline

    
    #     return a if b == 0 else GCD(b, a % b)

    class SegTree():
        def __init__(self, n_, ele_id, operation_func):
            self.n = 1
            while self.n < n_:
                self.n *= 2
            self.data = [ele_id] * (2 * self.n - 1)
            self.ele_id = ele_id
            self.operation_func = operation_func

        def __getitem__(self, idx):
            return self.data[idx + self.n - 1]

        def init(self, data_init):
            for i in range(len(data_init)):
                self.data[i + self.n - 1] = data_init[i]
            for i in range(self.n - 2, -1, -1):
                self.data[i] = self.operation_func(self.data[2 * i + 1],
                                                   self.data[2 * i + 2])

        def update(self, idx, x):
            
            idx += self.n - 1
            self.data[idx] = x
            while idx > 0:
                idx = (idx - 1) // 2
                self.data[idx] = self.operation_func(self.data[2 * idx + 1],
                                                     self.data[2 * idx + 2])

        def query(self, a, b):
            return self.query_(a, b, 0, 0, self.n)

        def query_(self, a, b, k, l, r):
            
            if r <= a or b <= l:
                
                return self.ele_id

            if a <= l and r <= b:
                
                return self.data[k]
            else:
                
                child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
                child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
                return self.operation_func(child_l, child_r)

    n = int(input())
    a = tuple(map(int, input().split()))
    seg_gcd = SegTree(n, 0, gcd)
    seg_gcd.init(a)

    ans = seg_gcd.data[0]
    for i in range(n):
        seg_gcd.update(i, 0)
        ans = max(ans, seg_gcd.data[0])
        seg_gcd.update(i, a[i])

    print(ans)


if __name__ == '__main__':
    main()


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

def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)

l = [0]
r = [0]
for i in range(n):
    l.append(GCD(l[i], a[i]))
    r.append(GCD(r[i], a[n-1 - i]))
r = r[::-1]

ans = 1
for i in range(n):
    ans = max(ans, GCD(l[i], r[i+1]))

print(ans)


Verdicts: Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Accepted