{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"题目背景","value":{"format":"MD","content":"在遥远的拉特兰国,每个拉特兰人都会拥有一些守护铳。一只守护铳按下扳机后,会发射出一定数目的子弹。\n\n今天!拉特兰首家线上守护铳贩卖店上线啦!打开APP就可以看到像我们的某宝一样的界面,许多商品如瀑布状从上到下一字排开(如图为某宝的商品列表),每只守护铳都有一个k_i,表示每按下一次扳机后发出子弹的个数。\n![image.png](https://i.loli.net/2020/06/04/J7VjDBaT6lguN8c.png)\n\n拉特兰首家线上守护铳贩卖店搞了一个大活动,新用户注册时可以进行一次抽奖,抽取一个数字n。表示这名用户可以免费获得页面上连续的n支守护铳。\n\n和丁丁妹一样贫穷的Exusiai酱当然不会放弃这次机会,并且,Exusiai酱会把她将从这次活动得到的n支守护铳作为她今后的全部守护铳。\n\n但是Exusiai酱的老板要求,为了执行任务时方便,Exusiai酱拥有的全部n支守护铳的 k_i 集合必须恰好为某个包含n个整数的区间内的全部整数的集合。比如说,Exusiai酱现在的“冲锋”、“扫射”、“过载”三把守护铳分别进行三连射、四连射、五连射,在执行任务时就会非常方便。\n\n又比如说,{3,4,5}、{2,3}、{9,10,11,12,13}、{5,2,4,3,1}、{3,1,2}都可能是合法的集合,而{1,3}、{2,3,5,6,7}、{6,1,5,2,4}都是不合法的集合。需要注意,N支守护铳的 k_i 集合的秩必须依然是N。\n\n现在Exusiai酱正趴在床上、盯着手机、等待着抽奖,嘴角眉梢流露出孩子般天真无邪的笑容。在这个紧张的时刻,她不住地向你倾诉,一遍遍地向你描绘她所畅想的无数种未来。她反复在问你这样的问题:对于抽奖可能得到的某一个 n_j ,Exusiai酱有**多少种**合法的可选方案? "}},{"title":"题目描述","value":{"format":"MD","content":"你可以将题目抽象为以下模型:\n\nExusiai酱有一个长度为len的供选择的守护铳列表。给定了第i支守护铳按下一次扳机后会发出的子弹数量k_i。\n\nExusiai酱会多次向你询问,第j次询问由输入给定一个n_j。你每次需要根据n_j统计守护铳列表中合法区间的数目。\n\n设一个区间从k_a开始,长度为n_j,这个区间里所有位置 { k_a , k_(a+1) , ... , k_(a+len-1) } 构成的集合为S,这个区间是合法的当且仅当:\n1)S包含了S中最大值与最小值构成的闭区间之间的所有整数。\n2)S的秩(元素个数)恰好为n_j。"}},{"title":"输入","value":{"format":"MD","content":"单组数据输入。\n输入的第一行,包含两个由空格分隔的整数len、m。\nlen(0 \u003c len ≤ 10000)表示守护铳列表的长度,m(0 ≤ m ≤ 10000)表示Exusiai酱向你询问的次数。\n第二行包含len个由空格分隔的正整数,第i个数字为k_i(0 \u003c k_i ≤ 2147483648),表示第i支守护铳按下一次扳机后,会发出的子弹数量。\n接下来的m行,每行一个正整数n_j(0 \u003c n_j ≤ 1000),表示Exusiai酱畅想的她可能需要选择的守护铳数目。"}},{"title":"输出","value":{"format":"MD","content":"# **输出的第一行输出“Case #1:”**\n接下来的m行,每行输出一个整数,表示对应的询问中合法区间的数目。"}},{"title":"样例","value":{"format":"MD","content":"**样例一:**\n输入:\n\n9 3\n1 2 3 1 2 3 4 5 6\n3\n4\n5\n\n输出:\n\nCase #1:\n7\n3\n2\n\n**样例二:**\n输入:\n\n12 5\n9 8 7 6 7 6 5 4 1 2 3 4\n2\n3\n4\n5\n6\n\n输出:\n\nCase #1:\n10\n6\n4\n1\n1\n\n\n"}}]}