问题 3669 --最长牛棚（2）

3669: 最长牛棚（2）

时间限制: 1 Sec  内存限制: 256 MB
提交: 162  解决: 55
[提交][状态][讨论版][命题人:]

题目描述

如果把一排牛棚的位置看成是一个数轴，那么在1-L的位置上，每个位置都有一个牛棚，一共有L个牛棚。现在，因为一场大风，把数个牛棚刮走了，只剩下最多n个牛棚。现在给你一个牛棚的编号，请你求出，从该牛棚编号开始向右（编号增大）的方向一共有多少个连续的牛棚。如果要询问的编号的牛棚已经被刮走了，输出0.可能会有多次查询。

输入

第一行两个整数n，刮风后剩余牛棚的数量。

第二行，n个整数ai。ai表示第ai个位置有牛（数字可能有重复，重复数字算1个牛棚）。

第三行，一个整数q,表示询问的次数

接下来q行，每行一个整数qi,表示询问的牛棚编号。

输出

一共q行，每行一个整数，表示要查询的连在一起的牛棚数量

样例输入

10
3 4 5 7 8 9 10 11 12 13
2
1
7

样例输出

0
7

提示


样例解释：



第1个查询的编号是1，编号1的牛棚不存在。所以输出0



第2个查询的编号是7，从7开始一共有7个牛棚连在一起。



数据范围。



50%的数据：1<=n<=1000  



100%的数据：1<=L<=10^6  0<=n<=L 1<=ai<=L 1<=qi<=L

来源

前缀和 

[提交][状态]