Description

Combinatory logic is a symbolic system invented by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. This problem considers a combinator system that slightly differs from the one in the real world.

A combinator term is one of the following forms:

Here $P$ denotes a primitive function, and $E_1$ and $E_2$ are combinator terms (they may be the same). Any expression not in the above forms is not a combinator term.

We define the number of arguments of a combinator term $E$, denoted $np(E)$, as follows:

$np(P)$ equals the number of arguments (arity) of the primitive function $P$.

$np((E_1\;E_2)) = np(E_1) - 1$.

In this problem, we use a positive integer to denote both a primitive function and the arity of that primitive function.

For a combinator term $E$, if $np$ of $E$ and of all combinator subterms it contains are positive integers, we say that $E$ is in normal form.

We often use a simplified notation for combinator terms: if a combinator term $E$ contains a consecutive subsequence $(… ((E_1\;E_2)\;E_3) …E_n)$ (where $n ≥ 3$), where each $E_k$ denotes a combinator term (which may itself be in simplified notation), then we replace that part by $(E_1\;E_2\;E_3 … E_n)$ while keeping the rest unchanged, obtaining a simplified representation of $E$. A combinator term may be simplified in this way multiple times.

Given a sequence of primitive functions, determine the minimum number of pairs of parentheses that must be added to make the expression a simplified representation of a normal form (i.e., it satisfies the normal-form property). If it is impossible to obtain a simplified representation of a normal form no matter how you add parentheses, output $-1$.

Input Format

The first line contains a positive integer $T$, the number of queries.

Then follow $2T$ lines.

Line $2k$ contains a positive integer $n_k$, the number of primitive functions in the sequence of the $k$-th query.

Line $2k + 1$ contains $n_k$ positive integers, where the $i$-th integer denotes the $i$-th primitive function in the sequence.

Output Format

Output $T$ lines, each containing one integer, the answer for the corresponding query.

2
5
3 2 1 3 2
5
1 1 1 1 1

3
-1

Hint

【Sample Explanation】

For the first query: an optimal plan is (3 (2 1) (3 2)). One can prove that there is no plan that uses fewer pairs of parentheses.

For the second query: it is easy to prove that no valid plan exists.

【Constraints】

Let $TN$ denote the sum of all $n_k$ in the input.

Translated by ChatGPT 5