G. el Coach
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The year is 2026, and the competitive programming scene is at its absolute peak. Homs-CPC and SVU-CPC are facing each other in a special challenge supervised by the legendary judge Kira and the strict coach Habbab.

To prepare for the challenge, the contestants are arranged in a fixed order. Each contestant has an integer $$$a_i$$$, representing their problem-solving skill level.

Coach Habbab wants to divide the contestants into exactly two distinct strategic groups during a crucial part of the contest: the Main Team and the Support Team.

You are given an array $$$a$$$ of $$$n$$$ integers, representing the skill levels of the contestants. Coach Habbab decides to choose a contiguous subarray from index $$$l$$$ to $$$r$$$ to form the Main Team. The remaining contestants (from index $$$1$$$ to $$$l-1$$$, and from $$$r+1$$$ to $$$n$$$) will form the Support Team. Due to his custom strategy, Coach Habbab must choose the indices such that $$$l \le r$$$ ($$$1 \le l \le r \le n$$$).

The "Judges' Score" of this strategy is calculated as the sum of two values:

1. The maximum skill level among the Main Team:

$$$$$$ \max(a[l], a[l+1], \dots, a[r]). $$$$$$

2. The MEX (Minimum Excluded value) of the skill levels among the Support Team:

$$$$$$ \operatorname{MEX}(a[1],a[2], \dots, a[l-1], a[r+1], a[r+2], \dots, a[n]). $$$$$$

(Note: The MEX of a set of integers is the smallest non-negative integer that does not belong to the set).

Kira and Coach Habbab want to find the best possible strategy that minimizes this total Judges' Score.

Help the contestants of Homs-CPC and SVU-CPC find the minimum possible score by choosing the optimal subarray $$$(l, r)$$$ under the condition $$$l \le r$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.

Then, $$$T$$$ test cases follow.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in the array $$$a$$$. The second line of each test case contains $$$n$$$ space-separated integers $$$a[1], a[2], \dots, a[n]$$$ ($$$0 \le a[i] \le 10^9$$$) — the skill levels of the players.

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

Output

For each test case, print a single integer on a new line — the minimum possible Judges' Score that Kira and Coach Habbab can achieve by choosing a valid subarray $$$(l,r)$$$ under the condition $$$l \le r$$$.

Example
Input
1
4
10 3 1 2
Output
1