CodeForces - 1610B Kalindrome Array

B. Kalindrome Array time limit per test1 second memory limit per test256 megabytes

An array [b₁,b₂,…,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₁,a₂,…,a_n]. Determine if a is kalindrome or not.

Input The first line contains a single integer t (1≤t≤10⁴) — 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≤n≤2?10⁵) — the length of the array.

The second line of each test case contains n integers a₁,a₂,…,a_n (1≤a_i≤n) — elements of the array.

It’s guaranteed that the sum of n over all test cases won’t exceed 2?10⁵.

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

Example input 4 1 1 2 1 2 3 1 2 3 5 1 4 4 1 4 output YES YES NO YES 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].

问题链接：CodeForces - 1610B Kalindrome Array 问题简述：（略） 问题分析：（略） AC的C 语言程序如下：

/* CodeForces - 1610B Kalindrome Array */  #include <bits/stdc .h>  using namespace std;  const int N = 200000   1; int a[N], b[N];  int main() { 
            int t;     scanf("%d", &t);     while (t--) { 
                int n;         scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        int x = 0, y = 0;
        for (int i = 1, j = n; i < j; i++, j--)
            if (a[i] != a[j]) { 
       
                x = a[i], y = a[j];
                break;
            }

        int flag = 1;
        if (x == 0 && y == 0)
            ;
        else { 
       
            flag = 1;
            int cnt = 0;
            for (int i = 1; i <= n; i++)
                if (a[i] != x) b[cnt++] = a[i];
            for (int i = 0, j = cnt - 1; i < j; i++, j--)
                if (b[i] != b[j]) { 
       
                    flag = 0;
                    break;
                }
            if ( flag )
                ;
            else { 
       
                flag = 1;
                cnt = 0;
                for (int i = 1; i <= n; i++)
                    if (a[i] != y) b[cnt++] = a[i];
                for (int i = 0, j = cnt - 1; i < j; i++, j--)
                    if (b[i] != b[j]) { 
       
                        flag = 0;
                        break;
                    }
            }
        }

        printf("%s\n", flag ? "YES" : "NO");
    }

    return 0;
}