Planting Trees

All submissions for this problem are available.

### Read problem statements in [Bengali](http://www.codechef.com/download/translated/LTIME78/bengali/DEADEND.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME78/mandarin/DEADEND.pdf), [Russian](http://www.codechef.com/download/translated/LTIME78/russian/DEADEND.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME78/vietnamese/DEADEND.pdf) as well. Kerim is an environment-friendly guy. Today, he accepted Samir's challenge of planting 20 million trees by 2020. Currently, there are $N$ trees (numbered $1$ through $N$) planted at distinct positions on a line; for each valid $i$, the position of the $i$-th tree is $A_i$. A set of trees is *beautiful* if for each tree in this set (let's denote its position by $x$), there is a tree at the position $x-1$ and/or a tree at the position $x+1$. Kerim's task is to plant some (possibly zero) trees in such a way that the resulting set of all planted trees (the initial $N$ trees and those planted by Kerim) is beautiful. It is only allowed to plant trees at integer (possibly negative) positions. Find the minimum number of trees he needs to plant in order to achieve that. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains a single integer $N$. - The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$. ### Output For each test case, print a single line containing one integer ― the minimum number of trees Kerim needs to plant. ### Constraints - $1 \le T \le 1,000$ - $1 \le N \le 10^5$ - $1 \le A_i \le 10^9$ for each valid $i$ - $A_1, A_2, \ldots, A_N$ are pairwise distinct - the sum of $N$ over all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (50 points):** - $N \le 1,000$ - $A_i \le 2,000$ for each valid $i$ - the sum of $N$ over all test cases does not exceed $10^4$ **Subtask #2 (50 points):** original constraints ### Example Input ``` 1 3 2 7 4 ``` ### Example Output ``` 2 ``` ### Explanation **Example case 1:** Kerim should plant trees at the positions $3$ and $6$ to make the grid beautiful, so the answer is $2$.