Kalindrome Array (Codeforces 1610B)
Tags: Greedy, two pointers

An array $$$[b_1, b_2, \ldots, b_m]$$$ is a palindrome, if $$$b_i = b_{m+1-i}$$$ for each $$$i$$$ from $$$1$$$ to $$$m$$$. Empty array is also a palindrome.An array is called kalindrome, if the following condition holds: It's possible to select some integer $$$x$$$ and delete some of the elements of the array equal to $$$x$$$, so that the remaining array (after gluing together the remaining parts) is a palindrome. Note that you don't have to delete all elements equal to $$$x$$$, and you don't have to delete at least one element equal to $$$x$$$.For example :   $$$[1, 2, 1]$$$ is kalindrome because you can simply not delete a single element.  $$$[3, 1, 2, 3, 1]$$$ is kalindrome because you can choose $$$x = 3$$$ and delete both elements equal to $$$3$$$, obtaining array $$$[1, 2, 1]$$$, which is a palindrome.  $$$[1, 2, 3]$$$ is not kalindrome. You are given an array $$$[a_1, a_2, \ldots, a_n]$$$. Determine if $$$a$$$ is kalindrome or not.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — elements of the array.It's guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print YES if $$$a$$$ is kalindrome and NO otherwise. You can print each letter in any case.

Note: In the first test case, array $$$[1]$$$ is already a palindrome, so it's a kalindrome as well.In the second test case, we can choose $$$x = 2$$$, delete the second element, and obtain array $$$[1]$$$, which is a palindrome.In the third test case, it's impossible to obtain a palindrome.In the fourth test case, you can choose $$$x = 4$$$ and delete the fifth element, obtaining $$$[1, 4, 4, 1]$$$. You also can choose $$$x = 1$$$, delete the first and the fourth elements, and obtain $$$[4, 4, 4]$$$.

Sample Inputs:
4
1
1
2
1 2
3
1 2 3
5
1 4 4 1 4

Sample Outputs:
YES
YES
NO
YES

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, arr) = (readInt(), readList())
    (f, b) = (0, n - 1)
    while f < b:
        if arr[f] == arr[b]:
            f += 1
            b -= 1
        else:
            a = [x for x in arr[f:b + 1] if x != arr[f]]
            b = [x for x in arr[f:b + 1] if x != arr[b]]
            if a == a[::-1] or b == b[::-1]:
                return 'YES'
            else:
                return 'NO'
    return 'YES'
for _ in range(int(input())):
    print(solve())

Solution (Python):
for r in [*open(0)][2::2]:
    m = r.split()
    i = len(m)
    while i and m[i - 1] == m[-i]:
        i -= 1
    print('YNEOS'[all((z != z[::-1] for z in ([x for x in m if x != y] for y in (m[i - 1], m[-i]))))::2])

Solution (Python):
for _ in [*open(0)][2::2]:
    i = len((a := _.split()))
    while (a[i - 1] == a[-i]) * i:
        i -= 1
    print('YNEOS'[all((v != v[::-1] for v in ([x for x in a if x != y] for y in (a[i - 1], a[-i]))))::2])