I. Inversion Test
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Schubert has recently been studying properties of arrays, and something that caught his attention is called inversions. From what he recalls from class, the number of inversions of an array $$$a$$$ of size $$$n$$$ is defined by the number of pairs $$$(i, j)$$$ such that $$$(1 \leq i \lt j \leq n)$$$, in which $$$(a_i \gt a_j)$$$. Schubert realized that given an array, there are plenty of subarrays whose number of inversions is the same as the original array. As such, he gave this simple task: given an array, find the size of the smallest subarray in which the number of inversions is the same as in the original array.

An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases that Schubert gives to you.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$ — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$(a_1, a_2, ..., a_n)$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$ — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, output a single integer in a separate line — the size of the smallest subarray in which the number of inversions is the same as the original one.

Examples
Input
2
4
49 0 2 -1
6
5 6 59 23 71 100
Output
4
2
Input
1
5
1 2 3 4 5
Output
0