P4505 [CTSC2013] Combinatory Logic

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: $$P$$ $$(E_1\;E_2)$$ 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$.

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 $T$ lines, each containing one integer, the answer for the corresponding query.

【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. 测试点编号|规模 :-:|:-: 1|$T ≤ 30, n_k ≤ 3$ 2|$T ≤ 30, n_k ≤ 15$ 3|$TN ≤ 100$ 4|$TN ≤ 500$ 5|$TN ≤ 2000$ 6|$TN ≤ 5000$ 7|$TN ≤ 5000$ 8|$TN ≤ 1000000$ 9|$TN ≤ 2000000$ 10|$TN ≤ 2000000$ Translated by ChatGPT 5