F. Cupcake Circle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Suzie the Cupcake Monster just pulled off a huge heist of $$$n$$$ cupcakes from the Cupcake Factory, with the $$$i$$$th cupcake having a deliciousness of $$$a_i.$$$ To celebrate, she plans to play a game as she eats her cupcakes.

Suzie will first arrange her cupcakes among $$$n$$$ equally spaced indices in a circle. Then, she will start at the first index and begin stepping along the indices of the circle in increasing order, with index $$$n$$$ wrapping around to $$$1$$$. Each time she reaches an index (including the index she starts at), Suzie may choose to eat the cupcake at that index if there is one. To make the game interesting, Suzie wants to eat all of the cupcakes in nondecreasing order of deliciousness (note this means for some cupcakes, she may need to skip over it at first and circle around to eat it later).

Suzie is growing hungry, so she wants to know, for a possible arrangement of her cupcakes, what is the minimum number of steps she must take if she wants to be able to eat all of the cupcakes in nondecreasing order of deliciousness?

Input

The first line contains $$$t$$$ $$$(1\leq t \leq 10^4)-$$$ the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(1\leq n \leq 2\cdot 10^5)-$$$ the number of cupcakes.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\dots, a_n$$$ $$$(1\leq a_i\leq 10^9)$$$, where $$$a_i$$$ is the deliciousness of the cupcake at index $$$i$$$ in the circle.

It is guaranteed the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output an integer, the minimum number of steps Suzie must take to eat all of the cupcakes in nondecreasing order of deliciousness.

Example
Input
3
5
1 2 3 4 5
5
1 4 4 2 3
1
100
Output
4
7
0
Note

For the first test case, Suzie can eat each cupcake in order of indices 1, 2, 3, 4, 5, so she just needs to take four steps to reach index 5, eating all the cupcakes as she goes.

For the second test case, Suzie can eat the cupcakes in order of indices 1, 4, 5, 2, 3, which requires her to take seven steps and wrap around the circle once, ending at index 3.

For the third test case, Suzie can eat the only cupcake without taking any steps.