Segment Tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
The segment tree is a data structure that is capable of processing different queries on the array in an efficient way.
A segment tree is usually created with the following routine.
createTree(left, right): currentNode = new node() currentNode>left = left currentNode>right = right currentNode>tag = 0 if (left < right): middle = (left + right) / 2 currentNode>leftSon = createTree(left, middle) currentNode>rightSon = createTree(middle + 1, right) return currentNode
The routine is called as:
root = init(1, N)
Consider the following segment tree operations:
changeSegtree(currentNode, left, right): currentNode>tag = 1 if (left == currentNode>left) and (right == currentNode>right) return newRight = min(right, currentNode>leftSon>right) if (left <= newRight): changeSegtree(currentNode>leftSon, left, newRight) newLeft = max(left, currentNode>rightSon>left) if (newLeft <= right): changeSegtree(currentNode>rightSon, newLeft, right) change(left, right): changeSegtree(root, left, right)
Finally, an inorder traversal of the tree can be done with the following routine:
traverse(currentNode): if (currentNode>leftSon != NULL) traverse(currentNode>leftSon) print currentNode>tag if (currentNode>rightSon != NULL) traverse(currentNode>rightSon) traverse(root)
You are given the value of N, denoting the length of the array on which the segment tree is built on (i.e. the second parameter to the init routine). You are also given M integers T_{1}, T_{2}, ..., T_{M}. Here, M is the number of nodes in the segment tree and you'll have calculate it by yourself.
Your task is to find the minimum number of nonoverlapping segments, so that after calling the change routine for each of these segments successively, on a newly created segment tree, the traverse routine will output T_{1}, T_{2}, ..., T_{M}, or state that such a set of segments doesn't exist.
Two segments (l_{1},r_{1}) and (l_{2},r_{2}) are considered overlapping if there is some i such that l_{1} ≤ i ≤ r_{1} and l_{2} ≤ i ≤ r_{2}.
Input
The first line of the input contains an 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 denoting the length of segment tree range.
The second line contains M spaceseparated integers T_{1}, T_{2}, ..., T_{M} denoting what the tags of the segment tree's nodes should be, in inorder traversal. Here, M is the number of nodes in the segment tree.
Output
For each test case, output a single line containing the minimum number of segments to modify. In case it's impossible to achieve the given configuration of tags, output 1.
Constraints
 1 ≤ T ≤ 5 × 10^{4}
 1 ≤ N ≤ 10^{5}
 1 ≤ Sum of N ≤ 5 × 10^{5}
Example
Input: 2 2 1 1 1 2 1 0 1 Output: 2 1
Explanation
Example case 1. We can call change(1, 1) and change(2, 2).
Example case 2. There is no set of segments that would give the tree with such configuration of tags.
Author:  xcwgf666 
Tags  xcwgf666 
Date Added:  23052016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 