Problem:


Score : 300 points

Problem Statement

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.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

Output

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Sample Input 1

3
7 6 8

Sample Output 1

2

If we replace 7 with 4, the greatest common divisor of the three integers on the blackboard will be 2, which is the maximum possible value.

Sample Input 2

3
12 15 18

Sample Output 2

6

Sample Input 3

2
1000000000 1000000000

Sample Output 3

1000000000

We can replace an integer with itself.



Sample input:
3
7 6 8


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class SegmentTree:

    def __init__(self, array, operator, identity):
        self.identity = identity
        self.operator = operator

        self.array_size = len(array)
        tree_height = (self.array_size - 1).bit_length()
        self.tree_size = 2 ** (tree_height + 1)
        self.leaf_start_index = 2 ** tree_height
        self.tree = [identity] * self.tree_size

        for i in range(self.array_size):
            self.tree[self.leaf_start_index + i] = array[i]

        for i in range(self.array_size - 1, 0, -1):
            self.tree[i] = self.operator(self.tree[i << 1], self.tree[i << 1 | 1])

    def update(self, index, val):
        cur_node = self.leaf_start_index + index
        self.tree[cur_node] = val

        while cur_node > 1:
            self.tree[cur_node >> 1] = self.operator(self.tree[cur_node], self.tree[cur_node ^ 1])
            cur_node >>= 1

    def query(self, begin, end):
        res = self.identity

        if begin < 0:
            begin = 0

        if end > self.array_size:
            return self.identity

        left = begin + self.leaf_start_index
        right = end + self.leaf_start_index

        while left < right:
            if left & 1:
                res = self.operator(res, self.tree[left])
                left += 1

            if right & 1:
                right -= 1
                res = self.operator(res, self.tree[right])

            left >>= 1
            right >>= 1

        return res


def main():
    from fractions import gcd

    n = int(input())
    a = list(map(int, readline().split()))
    seg = SegmentTree(a, gcd, 0)
    ans = 0

    for i in range(n):
        temp1 = seg.query(0, i)
        temp2 = seg.query(i + 1, n)
        temp = gcd(temp1, temp2)
        ans = max(ans, temp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class SegmentTree:

    def __init__(self, array, operator, identity):
        self.identity = identity
        self.operator = operator

        self.array_size = len(array)
        tree_height = (self.array_size - 1).bit_length()
        self.tree_size = 2 ** (tree_height + 1)
        self.leaf_start_index = 2 ** tree_height
        self.tree = [identity] * self.tree_size

        for i in range(self.array_size):
            self.tree[self.leaf_start_index + i] = array[i]

        for i in range(self.array_size - 1, 0, -1):
            self.tree[i] = self.operator(self.tree[i << 1], self.tree[i << 1 | 1])

    def update(self, index, val):
        cur_node = self.leaf_start_index + index
        self.tree[cur_node] = val

        while cur_node > 1:
            self.tree[cur_node >> 1] = self.operator(self.tree[cur_node], self.tree[cur_node ^ 1])
            cur_node >>= 1

    def query(self, begin, end):
        res = self.identity

        if begin < 0:
            begin = 0

        if end > self.array_size:
            end = self.array_size

        left = begin + self.leaf_start_index
        right = end + self.leaf_start_index

        while left < right:
            if left & 1:
                res = self.operator(res, self.tree[left])
                left += 1

            if right & 1:
                right -= 1
                res = self.operator(res, self.tree[right])

            left >>= 1
            right >>= 1

        return res


def main():
    from fractions import gcd

    n = int(input())
    a = list(map(int, readline().split()))
    seg = SegmentTree(a, gcd, 0)
    ans = 0

    for i in range(n):
        temp1 = seg.query(0, i)
        temp2 = seg.query(i + 1, n)
        temp = gcd(temp1, temp2)
        ans = max(ans, temp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
gcd1 = [0] * (N - 1)
gcd1[0] = A[0]
gcd2 = [0] * (N - 1)
gcd2[-1] = A[-1]
for i in range(N - 2):
    a, b = gcd1[i], A[i + 1]
    while b:
        a, b = b, a % b
    gcd1[i + 1] = a
    a, b = gcd2[-i-1], A[-i-2]
    while b:
        a, b = b, a % b
    gcd1[-i-2] = a
ans = max(gcd1[-1], gcd2[0])
for i in range(N - 2):
    a, b = gcd1[i], gcd2[i + 1]
    while b:
        a, b = b, a % b
    ans = max(a, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ns = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
from fractions import gcd
gcdl = [ns[0]]
gcdr = [ns[-1]]
for i in range(1, n):
    gcdl.append(gcd(gcdl[-1], ns[i]))
    gcdr.append(gcd(gcdr[-1], ns[-(i+1)]))
max_gcd = max(gcdr[-2], gcdl[-2])
for i in range(1, n-1):
    max_gcd = max(gcd(gcdl[i-1], gcdr[i-1]), max_gcd)
print(max_gcd)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

N = int(input())
A = list(map(int, input().split()))
left = [0]*N
right = [0]*N

left_gcd = A[0]
left[0] = A[0]
for i in range(1, N-1):
    left[i] = gcd(left_gcd, A[i])

right_gcd = A[-1]
right[-1] = A[-1]
for i in range(N-2, 0, -1):
    right[i] = gcd(right_gcd, A[i])

# print(left, right)
max_val = max(left[-2], right[1])
for i in range(1, N-1):
    max_val = max(max_val, gcd(left[i-1], right[i+1]))

print(max_val)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = iip()

    A.sort()
    A1 = [i for i in A]
    A2 = [i for i in A]

    ss1 = soinsuu_bunkai(A[0])
    ss2 = soinsuu_bunkai(A[1])
    ah1 = [1 for _ in A]
    ah2 = [1 for _ in A]


    #print(A)
    ak1 = 1
    for i in ss1:
        out = 0
        ahk = None
        for j, a in enumerate(A1):
            if a % i != 0:
                out += 1
                if out == 2: #2回アウトなら終了。
                    break
                else:
                    ahk = j
            else:
                A1[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah1[ahk] *= i
        else:
            ak1 *= i

    ak2 = 1
    for i in ss2:
        out = 0
        ahk = None
        for j, a in enumerate(A2):
            if a % i != 0:
                out += 1
                if out == 2: #2回アウトなら終了。
                    break
                else:
                    A2[j] //= i
                    ahk = j
            else:
                A2[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah2[ahk] *= i
        else:
            ak2 *= i

    #print(ak1)
    #print(ah1)
    #print(ak2)
    #print(ah2)
    print(max(ak1*max(ah1), ak2*max(ah2)))



#####################################################ライブラリ集ここから

def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = iip()

    A.sort()
    A1 = [i for i in A]
    A2 = [i for i in A]

    ss1 = soinsuu_bunkai(A[0])
    ss2 = soinsuu_bunkai(A[1])
    ah1 = [1 for _ in A]
    ah2 = [1 for _ in A]


    #print(A)
    ak1 = 1
    for i in ss1:
        out = 0
        ahk = None
        for j, a in enumerate(A1):
            if a % i != 0:
                out += 1
                if out == 2: #2回アウトなら終了。
                    break
                else:
                    ahk = j
            else:
                A1[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah1[ahk] *= i
        else:
            ak1 *= i

    ak2 = 1
    for i in ss2:
        out = 0
        ahk = None
        for j, a in enumerate(A2):
            if a % i != 0:
                out += 1
                if out == 2: #2回アウトなら終了。
                    break
                else:
                    A2[j] //= i
                    ahk = j
            else:
                A1[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah2[ahk] *= i
        else:
            ak2 *= i

    #print(ak1)
    #print(ah1)
    #print(ak2)
    #print(ah2)
    print(max(ak1*max(ah1), ak2*max(ah2)))



#####################################################ライブラリ集ここから

def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = iip()

    A.sort()
    A1 = [i for i in A]
    A2 = [i for i in A]

    ss1 = soinsuu_bunkai(A[0])
    ss2 = soinsuu_bunkai(A[1])
    ah1 = [1 for _ in A]
    ah2 = [1 for _ in A]


    #print(A)
    ak1 = 1
    for i in ss1:
        out = 0
        ahk = None
        for j, a in enumerate(A1):
            if a % i != 0:
                out += 1
                if out == 2: #2回アウトなら終了。
                    break
                else:
                    ahk = j
            else:
                A1[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah1[ahk] *= i
        else:
            ak1 *= i

    ak2 = 1
    for i in ss2:
        out = 0
        ahk = None
        for j, a in enumerate(A2):
            if a % i != 0:
                out += 1
                if out == 2: #2回アウトなら終了。
                    break
                else:
                    A2[j] //= i
                    ahk = j
        if out == 2:
            continue
        elif out == 1:
            ah2[ahk] *= i
        else:
            ak2 *= i

    #print(ak1)
    #print(ah1)
    #print(ak2)
    #print(ah2)
    print(max(ak1*max(ah1), ak2*max(ah2)))



#####################################################ライブラリ集ここから

def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = iip()

    A.sort()
    A1 = [i for i in A]
    A2 = [i for i in A]

    ss1 = soinsuu_bunkai(A[0])
    ss2 = soinsuu_bunkai(A[1])
    ah1 = [1 for _ in A]
    ah2 = [1 for _ in A]

    ak1 = 1
    for i in ss1:
        out = 0
        ahk = None
        for j, a in enumerate(A1):
            if a % i != 0:
                out += 1
                if out == 2: #2回アウトなら終了。
                    break
                else:
                    ahk = j
            A1[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah1[ahk] *= i
        else:
            ak1 *= i


    ak2 = 1
    for i in ss2:
        out = 0
        ahk = None
        for j, a in enumerate(A2):
            if a % i != 0:
                out += 1
                if out == 2: #2回アウトなら終了。
                    break
                else:
                    A2[j] //= i
                    ahk = j
        if out == 2:
            continue
        elif out == 1:
            ah2[ahk] *= i
        else:
            ak2 *= i

    #print(ak1)
    #print(ah1)
    #print(ak2)
    #print(ah2)
    print(max(ak1, ak2))



#####################################################ライブラリ集ここから

def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2-1)
        self.f = f

    def update(self, i, x):
        i += self.size-1
        self.dat[i] = x
        while i > 0:
            i = (i-1) >> 1
            self.dat[i] = self.f(self.dat[i*2+1], self.dat[i*2+2])

    def query(self, l, r, k=0, L=0, R=None):
        if R is None:
            R = self.size
        if R <= l or r <= L:
            return self.default
        if l <= L and R <= r:
            return self.dat[k]
        else:
            lres = self.query(l, r, k*2+1, L, (L+R) >> 1)
            rres = self.query(l, r, k*2+2, (L+R) >> 1, R)
            return lres + rres

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

n = int(input())
a = list(map(int, input().split()))
s = SegmentTree(n, gcd)
for i in range(n):
    s.update(i,a[i])

ans = 1
for i in range(n):
    left = s.query(0,i)
    right = s.query(i+1,n)
    res = gcd(left, right)
    if ans < res:
        ans = res
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
D = [A[i+1]-A[i] for i in range(len(A)-1)]
print(D)

if N == 2:
  print(max(A))
elif len(set(A))==1:
  print(A[0])
else:
  for i in reversed(range(min(A)+1)):
    cnt = 0
    for a in A:
      if a%i != 0:
        cnt = cnt+1
    if cnt <=1:
      print(i)
      break

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def gcd(n,m):
    if m == 0:
        return n
    else:
        return gcd(m,n%m)

n = I()
a = LI()
l = [0]*n
r = [0]*n
l[0] = a[0]
for i in range(1,n):
    l[i] = gcd(l[i-1],a[i])
r[-1] = a[-1]
for i in range(n-1):
    r[i] = gcd(r[i+1],a[i])

ans = 0
for i in range(n):
    if i == 0:
        ans = max(ans,r[i+1])
    elif i == n-1:
        ans = max(ans,l[-2])
    else:
        ans = max(ans,gcd(l[i-1],r[i+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = list(set(A))
A = sorted(A)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    
    return divisors

if len(A) <= 2:
    print(max(A))
    exit()
else:
    all_divisors = list(set(make_divisors(A[-1]) + make_divisors(A[-2])))

ans = 1
for divisor in all_divisors:
    cnt = 0
    for a in A:
        if a % divisor != 0:
            cnt += 1
        if cnt == 2:
            break
    if cnt < 2:
        ans = max(ans, divisor)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = list(set(A))
A = sorted(A)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    
    return divisors

if len(A) <= 2:
    print(max(A))
    exit()
else:
    all_divisors = list(set(make_divisors(A[0]) + make_divisors(A[1]) + make_divisors(A[2])))

ans = 1
for divisor in all_divisors:
    cnt = 0
    for a in A:
        if a % divisor != 0:
            cnt += 1
        if cnt == 2:
            break
    if cnt < 2:
        ans = max(ans, divisor)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = list(set(A))
A = sorted(A)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    
    return divisors

if len(A) <= 2:
    print(max(A))
    exit()
else:
    all_divisors = list(set(make_divisors(A[0]) + make_divisors(A[1])))

ans = 1
for divisor in all_divisors:
    cnt = 0
    for a in A:
        if a % divisor != 0:
            cnt += 1
        if cnt == 2:
            break
    if cnt < 2:
        ans = max(ans, divisor)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = list(set(A))
A = sorted(A)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    
    return divisors

if len(A) == 1:
    print(A[0])
    exit()
else:
    all_divisors = list(set(make_divisors(A[0]) + make_divisors(A[1])))

ans = 1
for divisor in all_divisors:
    cnt = 0
    for a in A:
        if a % divisor != 0:
            cnt += 1
        if cnt == 2:
            break
    if cnt < 2:
        ans = max(ans, divisor)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = list(set(A))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

if len(A) == 1:
    print(A[0])
    exit()
else:
    all_divisors = list(set(make_divisors(A[0]) + make_divisors(A[1])))

ans = 1
for divisor in all_divisors:
    cnt = 0
    for a in A:
        if a % divisor != 0:
            cnt += 1
        if cnt == 2:
            break
    if cnt < 2:
        ans = max(ans, divisor)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

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

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

gcd_left = []
tmp = A[0]
for i in range(N):
    tmp = gcd(tmp, A[i])
    gcd_left.append(tmp)

gcd_right = []
tmp = A[-1]
for i in range(N-1, -1, -1):
    tmp = gcd(tmp, A[i])
    gcd_right.append(tmp)
ans = 0
for i in range(len(A)):
    if i == 0:
        ans = max(ans, gcd_right[-2])
    elif i == len(A) - 1:
        ans = max(ans, gcd_left[-2])
    else:
        ans = max(ans, gcd(gcd_left[i-1], gcd_right[i-1]))

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from functools import reduce
    from fractions import gcd
    from collections import deque

    n, *a = map(int, open(0).read().split())
    q = deque(a)
    ans = 0
    for i in range(n):
        t = q.popleft()
        g = reduce(gcd, q)
        ans = max(ans, g)
        q.append(t)
        q.rotate(-1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

import math
def make_divisors(n):
    D=[]
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            D.append(i)
            if i!=n//i:
                D.append(n//i)
    D.sort()
    return D

n=int(input())
A=list(sorted(map(int,input().split())))
D0=list(reversed(make_divisors(A[0])))
D1=list(reversed(make_divisors(A[1])))

print(D0,D1)
ans=1
for d in D0:
    if d==1:
        continue
    cnt=0
    for a in A:
        if a%d!=0:
            cnt+=1
        if cnt>1:
            break
    if cnt<=1:
        ans=max(d,ans)
        break

for d in D1:
    if d==1:
        continue
    cnt=0
    for a in A:
        if a%d!=0:
            cnt+=1
        if cnt>1:
            break
    if cnt<=1:
        ans=max(d,ans)
        break

print(ans)