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):
import sys
import fractions
input = sys.stdin.readline
import heapq


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A_sorted = sorted(A)

    if len(A) == 2:
        print(max(A))
        exit()

    h = []
    heapq.heappush(h, fractions.gcd(A_sorted[0], A_sorted[-1]))
    for i in range(N - 1):
        heapq.heappush(h, fractions.gcd(A_sorted[i], A_sorted[i + 1]))

    heapq.heappop(h)
    heapq.heappop(h)

    gcd = 0
    while len(h) > 0:
        x = heapq.heappop(h)
        gcd = fractions.gcd(x, gcd)

    print(gcd)

if __name__ == '__main__':
    main()



import sys
import fractions
input = sys.stdin.readline
import heapq


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    h = []
    for a in A:
        heapq.heappush(h, -a)

    if len(A) == 2:
        print(max(A))
        exit()

    x = -heapq.heappop(h)
    y = -heapq.heappop(h)
    z = -heapq.heappop(h)

    xy = fractions.gcd(x, y)
    yz = fractions.gcd(y, z)
    xz = fractions.gcd(x, z)

    gcd = max([xy, yz, xz])

    while len(h) > 0:
        x = -heapq.heappop(h)
        gcd = fractions.gcd(gcd, x)

    print(gcd)



if __name__ == '__main__':
    main()



import sys
import fractions
input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A_sorted = sorted(A)

    if len(A) == 2:
        print(max(A))
        exit()

    gcd1 = fractions.gcd(A_sorted[0], A_sorted[1])
    gcd2 = fractions.gcd(A_sorted[1], A_sorted[2])
    gcd3 = fractions.gcd(A_sorted[0], A_sorted[2])
    gcd4 = 0

    is_skipped = False
    for i in range(3, N):
        tmp = fractions.gcd(gcd1, A[i])
        if is_skipped:
            gcd1 = tmp
            gcd4 = fractions.gcd(gcd3, A[i])
        else:
            if tmp < gcd1:
                gcd4 = tmp
                is_skipped = True

        gcd2 = fractions.gcd(gcd2, A[i])
        gcd3 = fractions.gcd(gcd3, A[i])

    print(max([gcd1, gcd2, gcd3, gcd4]))

if __name__ == '__main__':
    main()



import sys
import fractions
input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A_sorted = sorted(A)

    if len(A) == 2:
        print(max(A))
        exit()

    gcd1 = fractions.gcd(A_sorted[0], A_sorted[1])
    gcd2 = fractions.gcd(A_sorted[1], A_sorted[2])
    gcd3 = fractions.gcd(A_sorted[0], A_sorted[2])
    gcd4 = 0

    is_skipped = False
    for i in range(3, N):
        tmp = fractions.gcd(gcd1, A[i])
        if is_skipped:
            gcd1 = tmp
            gcd4 = fractions.gcd(gcd4, A[i])
        else:
            if tmp < gcd1:
                gcd4 = tmp
                is_skipped = True

        gcd2 = fractions.gcd(gcd2, A[i])
        gcd3 = fractions.gcd(gcd3, A[i])

    print(max([gcd1, gcd2, gcd3, gcd4]))

if __name__ == '__main__':
    main()



import sys
import fractions
input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A_sorted = sorted(A)

    if len(A) == 2:
        print(max(A))
        exit()

    gcd1 = fractions.gcd(A_sorted[0], A_sorted[1])
    gcd2 = fractions.gcd(A_sorted[1], A_sorted[2])
    gcd3 = fractions.gcd(A_sorted[0], A_sorted[2])
    gcd4 = 0

    is_skipped = False
    is_second_skipped = False
    for i in range(3, N):
        tmp = fractions.gcd(gcd1, A[i])
        if is_skipped:
            gcd1 = tmp
            tmp2 = fractions.gcd(gcd4, A[i])
            if is_second_skipped:
                gcd4 = tmp2
            else:
                if tmp2 < gcd4:
                    is_second_skipped = True
        else:
            if tmp < gcd1:
                gcd4 = tmp
                is_skipped = True

        gcd2 = fractions.gcd(gcd2, A[i])
        gcd3 = fractions.gcd(gcd3, A[i])

    print(max([gcd1, gcd2, gcd3, gcd4]))

if __name__ == '__main__':
    main()



import fractions

N = int(input())
A = [int(x) for x in input().split()]

minimum = 10 ** 10
minimum_index = 0


for i in range(N - 1):
    x = fractions.gcd(A[i], A[i + 1])
    if x < minimum:
        minimum = x
        minimum_index = i
  
gcd = 0      
for i in range(N - 1):
    if i == minimum_index or i == minimum_index + 1:
        continue
    
    if gcd == 0:
        gcd = A[i]
    else:
        gcd = fractions.gcd(gcd, A[i])

x = fractions.gcd(gcd, A[minimum_index])
y = fractions.gcd(gcd, A[minimum_index + 1])

print(max(x, y))


import sys
import fractions
input = sys.stdin.readline
import heapq


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A_sorted = sorted(list(set(A)))

    if len(A_sorted) <= 2:
        print(max(A_sorted))
        exit()

    min = 10 ** 10
    min_index = -1
    for i in range(N - 1):
        x = fractions.gcd(A_sorted[i], A_sorted[i + 1])
        if min > x:
            min = x
            min_index = i

    gcd = A_sorted[0]
    if min_index == 0:
        gcd = A_sorted[2]

    for i in range(N):
        if i == min_index or i == min_index + 1:
            continue
        gcd = fractions.gcd(gcd, A_sorted[i])

    x = fractions.gcd(gcd, A_sorted[min_index])
    y = fractions.gcd(gcd, A_sorted[min_index + 1])

    print(max([x, y]))

if __name__ == '__main__':
    main()



import sys
import fractions
input = sys.stdin.readline
import heapq


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A_sorted = sorted(set(A))

    if len(A) == 2:
        print(max(A))
        exit()

    min = 10 ** 10
    min_index = -1
    for i in range(N - 1):
        x = fractions.gcd(A_sorted[i], A_sorted[i + 1])
        if min > x:
            min = x
            min_index = i

    gcd = A_sorted[0]
    if min_index == 0:
        gcd = A_sorted[2]

    for i in range(N):
        if i == min_index or i == min_index + 1:
            continue
        gcd = fractions.gcd(gcd, A_sorted[i])

    x = fractions.gcd(gcd, A_sorted[min_index])
    y = fractions.gcd(gcd, A_sorted[min_index + 1])

    print(max([x, y]))

if __name__ == '__main__':
    main()



import fractions

N = int(input())
A = [int(x) for x in input().split()]

minimum = 10 ** 10
minimum_index = 0

x = 0
for i in range(N):
    if i == N - 1:
        x = fractions.gcd(A[i], A[0])
    else:
        x = fractions.gcd(A[i], A[i + 1])
    if x < minimum:
        minimum = x
        minimum_index = i
  
gcd = 0      
for i in range(N):
    if i == minimum_index or i == minimum_index + 1:
        continue
    
    if gcd == 0:
        gcd = A[i]
    else:
        gcd = fractions.gcd(gcd, A[i])

x = fractions.gcd(gcd, A[minimum_index])
y = 0
if minimum_index != N - 1:
    y = fractions.gcd(gcd, A[minimum_index + 1])
else:
    y = fractions.gcd(gcd, A[0])

print(max(x, y))


import sys
import fractions
input = sys.stdin.readline
import heapq


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A_sorted = sorted(A)

    if len(A) == 2:
        print(max(A))
        exit()

    min = 10 ** 10
    min_index = -1
    for i in range(N - 1):
        x = fractions.gcd(A_sorted[i], A_sorted[i + 1])
        if min > x:
            min = x
            min_index = i

    gcd = A_sorted[0]
    if min_index == 0:
        gcd = A_sorted[2]

    for i in range(N):
        if i == min_index or i == min_index + 1:
            continue
        gcd = fractions.gcd(gcd, A_sorted[i])

    x = fractions.gcd(gcd, A_sorted[min_index])
    y = fractions.gcd(gcd, A_sorted[min_index + 1])

    print(max([x, y]))

if __name__ == '__main__':
    main()



import sys
import fractions
input = sys.stdin.readline
import heapq

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

def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A_sorted = sorted(A)
    div0 = make_divisors(A_sorted[0])
    ans = 1
    for d in div0[1:]:
        count = 0
        isAns = True
        for i in A_sorted[1:]:
            if i % d != 0:
                count += 1
                if count == 2:
                    isAns = False
                    break
        if isAns:
            ans = max(ans, d)
    div1 = make_divisors(A_sorted[1])
    for d in div1[1:]:
        count = 0
        isAns = True
        for i in A_sorted[2:]:
            if i % d != 0:
                isAns = False
                break
        if isAns:
            ans = max(ans, d)

    print(ans)

if __name__ == '__main__':
    main()



Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Accepted