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 functools import lru_cache


@lru_cache(maxsize=None)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def sub():
    N, As = [input() for _ in range(2)]
    N = int(N)
    As = [int(e) for e in As.split(" ")]
    

    memG = 0
    if N == 2:
        memG = gcd(As[0], As[1])
    else:
        gLeft = {1: gcd(As[0], As[1])}
        for i in range(2, N):
            gI = gcd(gLeft[i - 1], As[i])
            gLeft[i] = gI

        gRight = {N - 2: gcd(As[N - 1], As[N - 2])}
        for i in range(2, N):
            gI = gcd(gRight[N - i], As[N - 1 - i])
            gRight[N - 1 - i] = gI

        for i in range(N):
            leftG = None
            if i - 1 in gLeft:
                leftG = gLeft[i - 1]
            rightG = None
            if i + 1 in gRight:
                rightG = gRight[i + 1]
            if leftG is None:
                memG = rightG
            elif rightG is None:
                memG = leftG
            else:
                memG = gcd(leftG, memG)

        
        #     tmp = As[:i] + As[i + 1 :]
        #     gI = gcd(tmp[0], tmp[1])
        #     tmp = tmp[2:]
        #     for t in tmp:
        #         gI = gcd(t, gI)
        #         if gI < memG:
        #             break
        #     if gI > memG:
        #         memG = gI
    print("{}".format(memG))


sub()


from functools import lru_cache, reduce


@lru_cache(maxsize=None)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def sub():
    N, As = [input() for _ in range(2)]
    N = int(N)
    As = [int(e) for e in As.split(" ")]
    

    memG = 0
    # if N == 2:
    # memG = gcd(As[0], As[1])
    # if N < 3:
    
    #         tmp = As[:i] + As[i + 1 :]
    #         g = reduce(gcd, tmp)
    #         if g > memG:
    #             memG = g
    if N == 2:
        memG = max(As)
    else:
        gLeft = {0: As[0], 1: gcd(As[0], As[1])}
        for i in range(2, N):
            gI = gcd(gLeft[i - 1], As[i])
            gLeft[i] = gI
        gRight = {N - 1: As[N - 1], N - 2: gcd(As[N - 1], As[N - 2])}
        for i in range(2, N):
            gI = gcd(gRight[N - i], As[N - 1 - i])
            gRight[N - 1 - i] = gI

        buf = []
        for i in range(N):
            leftG = None
            if (i - 1) in gLeft:
                leftG = gLeft[i - 1]
            rightG = None
            if (i + 1) in gRight:
                rightG = gRight[i + 1]
            # tmpG = None
            if leftG is None:
                leftG = rightG
            elif rightG is None:
                rightG = leftG
            buf.append(gcd(leftG, rightG))
            # tmpG = gcd(leftG, rightG)
            # if tmpG > memG:
            #     memG = tmpG
        memG = max(buf)

    print("{}".format(memG))


sub()


Verdicts: Wrong Answer

Accepted