• 电话：400-990-0325

# CodeForces - 1610B Kalindrome Array

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

An array [b1,b2,…,bm] is a palindrome, if bi=bm 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 [a1,a2,…,an]. Determine if a is kalindrome or not.

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

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤n) — elements of the array.

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

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  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 , 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].

AC的C 语言程序如下：

``````/* CodeForces - 1610B Kalindrome Array */  #include   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;
}
``````