Palindrome Detector

KOI Corporation is promoting its algorithm competition with a new challenge! You are given a secret sequence (S) of length (N) consisting of integers between 1 and 5000. Your task is to determine whether (S) is a palindrome. A sequence (S) is called a palindrome if and only if (S[i] = S[N-1-i]) for all (0 \le i \le N-1). For example, the sequences [1, 2, 3, 2, 1] and [1, 2, 2, 1] are palindromes, while [1, 2, 3, 1] and [1, 2, 2] are not.

To help participants, KOI provides two special machines which your program can call:

1. count_pair(x, y, z)

   • Input: three distinct indices (x, y, z) (each in the range ([0, N-1])).
   • It returns the number of equal pairs among the elements (S[x], S[y], S[z]). In particular, if (S[x] = S[y] = S[z]) it returns (3), if only two of them are equal it returns (1), otherwise it returns (0).

2. find_character(x, Y)

   • Input: an index (x) and a list of indices (Y) (each in the range ([0, N-1])).
   • It returns (1) if there exists an index (y \in Y) such that (S[x] = S[y]); otherwise, it returns (0).

Your task is to implement the function

int guess_palindromicity(int N);

which returns (1) if (S) is a palindrome and (0) otherwise. In your implementation, you should use the two machines efficiently. (Note: in a simulated environment, you are provided the entire secret sequence (S) as input, and you can implement the machines accordingly.)

The following constraints apply for each call to guess_palindromicity:

• You may call count_pair at most (2N) times.
• You may call find_character at most (N) times, and the total number of elements in all lists (Y) does not exceed (N).

Good luck!

inputFormat

The input begins with an integer (T) (the number of test cases). Each test case starts with an integer (N) (the length of the sequence (S)). The next line contains (N) space-separated integers representing the sequence (S), where each integer is between 1 and 5000.

outputFormat

For each test case, output a single line containing (1) if the sequence (S) is a palindrome, or (0) otherwise.

sample

1
5
1 2 3 2 1

1