Trees

Today CodeFamer is going to cut trees.There are $N$ trees standing in a line. They are numbered from $1$ to $N$. The tree numbered $i$ has height ${h_i}$. We say that two uncutted trees whose numbers are $x$ and $y$ are in the same block if and only if they are fitting in one of blow rules:

1)x+1=y or y+1=x;

2)there exists an uncutted tree which is numbered $z$, and $x$ is in the same block with $z$, while $y$ is also in the same block with $z$.

Now CodeFamer want to cut some trees whose height is not larger than some value, after those trees are cut, how many tree blocks are there?

Multi test cases (about $15$).

For each case, first line contains two integers $N$ and $Q$ separated by exactly one space, N indicates there are $N$ trees, $Q$ indicates there are $Q$ queries.

In the following $N$ lines, there will appear $h[1],h[2],h[3],…,h[N]$ which indicates the height of the trees.

In the following $Q$ lines, there will appear $q[1],q[2],q[3],…,q[Q]$ which indicates CodeFamer’s queries.

Please process to the end of file.

[Technical Specification]

$1 \leq N,Q \leq 50000$

$0 \leq h[i] \leq 1000000000(10^{9})$

$0 \leq q[i] \leq 1000000000(10^{9})$

For each $q[i]$, output the number of tree block after CodeFamer cut the trees whose height are not larger than $q[i]$.

3 2
5
2
3
6
2

0
2

In this test case, there are 3 trees whose heights are 5 2 3.

For the query 6, if CodeFamer cuts the tree whose height is not large than 6, the height form of left trees are -1 -1 -1(-1 means this tree was cut). Thus there is 0 block.

For the query 2, if CodeFamer cuts the tree whose height is not large than 2, the height form of left trees are 5 -1 3(-1 means this tree was cut). Thus there are 2 blocks.

BestCoder Round #36 ($)