Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

EP-Palindromes

By Hasinur_ · Limits 2s, 512 MB

You will be given an array of integers $A$. You have to count the number of $\textbf{subarrays}$ (a non-empty sequence of consecutive elements of an array) of $A$ that are EP-Palindrome.

Definition of EP-Palindrome

An array $V$ is EP-Palindrome if $|V|\mod 2 = 0$ and rearranging the elements in $V$ can form a palindrome. Here, $|V|$ denotes the number of elements in $V$, also known as the length of $V$. For example, let $V=[1,2,1,2] $ where $|V|\mod 2 = 0$. We can get $V= [1,2,2,1]$ or $V= [2,1,1,2] $ by rearranging the elements of $V$. So, $V=[1,2,1,2] $ is an $EP-Palindrome$.

Input

The first line of the input file will contain an integer $T (1\leq T\leq 30)$ which denotes the number of test cases. Then there will be $T$ test cases.

The first line of each test case will contain a single integer $N (1\leq N\leq10^{5})$, denoting the size of the array $A$.

The second line of each test case will contain $N$ integers $A[1], A[2], \dots, A[N]$ which are the elements of the array. Here, the $i^{th}$ integer denotes the element $A[i] (1\leq A[i]\leq 2\times10^{6})$.

Output

For each test case, print “$\textbf{Case X: Y}$” without the quotation symbol, where $X$ is the case number and $Y$ is the number of $EP-Palindromic$ subarrays of $A$.

Sample

InputOutput
2
3
1 1 1
4
1 2 1 2
Case 1: 2
Case 2: 1

In the sample input, the first test case contains an array $A[ ]=[1,1,1]$. Subarrays of $A$ are $[1],[1],[1],[1,1],[1,1],[1,1,1]$

Now,

  • $[1]$ has length $= 1$, $1 \mod 2 \neq 0$. So, it’s not EP-Palindrome.
  • $[1]$ has length $= 1$, $1 \mod 2 \neq 0$. So, it’s not EP-Palindrome.
  • $[1]$ has length $= 1$, $1 \mod 2 \neq 0$. So, it’s not EP-Palindrome.
  • $[1,1]$ has length $= 2$, $2 \mod 2 = 0$. The subarray is a palindrome already. So, $\textbf{it's EP-Palindrome}$.
  • $[1,1]$ has length $= 2$, $2 \mod 2 = 0$. The subarray is a palindrome already. So, $\textbf{it's EP-Palindrome}$.
  • $[1,1,1]$ has length $= 3$, $3 \mod 2 \neq 0$. So, it’s not EP-Palindrome.

The array $A$ has $2$ subarrays in total which are $\textbf{EP-Palindromes}$

    Discussion

    Statistics


    56% Solution Ratio

    aniks2645Earliest, 2M ago

    pathanFastest, 0.7s

    Test2311Lightest, 7.3 MB

    RUHRUHShortest, 531B

    Submit

    Login to submit

    Editorial

    Let’s first solve the problem considering the array as a string with lowercase latin letters. Then t...

    Related Contests