Trees

Accepts: 156
Submissions: 533
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
今天CodeFamer去坎树。有$N$棵树排成一排。他们被从$1$到$N$标号。第$i$号树的高度为${h_i}$。两棵未被坎掉的树编号分别为$x,y$当且仅当他们满足如下条件中一条时,他们是属于同一个块的:
1) x+1=y 或 y+1=x;
2) 存在一个棵未被坎掉的树,编号为$z$,$x$和$z$在同一个块并且$y$和$z$也在同一个块。
现在CodeFamer想要坎掉一些高度不大于某个值的树,坎掉之后会形成多少个块呢?
输入描述
多组测试数据(大概$15$组)
对于每一组数据,第一行包含两个整数$N$和$Q$,以一个空格分开,$N$表示有$N$棵树,$Q$表示有$Q$个查询。
在接下来的$N$行中,会出现$h[1],h[2],h[3],…,h[N]$,表示$N$棵树的高度。
在接下来的$Q$行中,会出现$q[1],q[2],q[3],…,q[Q]$表示CodeFamerr查询。

请处理到文件末尾。

[参数约定]
$1 \leq N,Q \leq 50000$
$0 \leq h[i] \leq 1000000000(10^{9})$
$0 \leq q[i] \leq 1000000000(10^{9})$
输出描述
对于每一个q[i],输出CodeFamer坎掉高度不大于q[i]的树之后有多少个块。
输入样例
3 2
5
2
3
6
2
输出样例
0
2
Hint
在这个样例中,有3棵树,他们的高度依次是5 2 3。

对于6这个查询,如果CodeFamer坎掉高度不大于6的树,那么剩下的树高度形状是-1 -1 -1(-1表示那个树被坎掉了)。这样就有0个块。

对于2这个查询,如果CodeFamer坎掉高度不大于2的树,那么剩下的树高度形状是5 -1 3(-1表示那个树被坎掉了)。这样就有2个块。