You are given a circular array of length $N$. You want to make the first two elements of the array equal.

Note

• A circular array is an array that contains elements in such a way that $A_{i+1}$ is the next element of $A_{i}$,..., $A_1$ is the next element of $A_N$.
• You can swap any two adjacent elements.

Your task is to determine the minimum number of swapping required to make the first two elements equal.

Example

Consider N = 7 and the circular array as {-1, 3, 4, -3, 3, -1, 2},

First operation, Swap numbers at index 1, 2 to get new array as {3, -1, 4, -3, 3, -1, 2},

Second operation, Swap numbers at index 6, 7 to get new array as {3, -1, 4, -3, 3, 2, -1},

Third operation, Swap numbers at index 1, 7 to get new array as {-1, -1, 4, -3, 3, 2, 3},

Therefore requires three swap operations. (Assuming 1-based indexing).

Function description

Complete the solve function provided in the editor. This function takes the following 2 parameters and returns the minimum number of swapping required:

N: An Integer representing the length of the array.

A: An Array of length N representing the elements of array A. 

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains an integer $T$ denoting the number of test cases.
• For each test case:
  • The first line contains an integer $N$.
  • The second line contains $N$ space-separated integers.

Output format

For each test case, print the minimum number of swaps required to make the first two elements equal. If you can not perform this, print -1.

Constraints

$1 \le T \le 10^5 \\ 1 \leq N \leq 2\times 10^{5} \\ -10^9 \leq A_i \leq 10^9$

The total sum of $N$ does not exceed $2\times10^5$.

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.