33OJ
登录 注册

#P17810. [ICPC 2019 Nanchang R] Eating Plan

[ICPC 2019 Nanchang R] Eating Plan

题目描述

Bob 现在饿了,需要吃点食物。Alice 把 nn 盘食物摆在他面前,编号从 11 到 nn。Alice 告诉他只能吃连续编号的若干盘食物,否则他会食物中毒。例如,若有 1010 盘食物,他可以吃第 22、33 和 44 盘中的食物,但不能吃第 22、33 和 55 盘中的食物,因为中间隔着第 44 盘,不连续。此外,如果他选择吃第 ii 盘食物,他必须吃掉该盘中的所有食物。

Bob 的胃有一个奇怪的特点:如果其中的食物至少有 t (=998857459)t~(=998857459) kg,胃里的食物重量会反复减少 tt kg,直到严格低于 tt kg 为止。同样地,如果胃里食物的重量恰好等于 tt kg,他的胃就会变空。现在 Bob 希望吃最少的连续盘数,使得胃里最终剩下的食物不少于 kk kg。你能告诉他最少需要选择多少盘吗?

输入格式

第一行包含两个整数 nn 和 mm(1≤n≤1000001\leq n\leq 100000,1≤m≤100001\leq m\leq 10000),分别表示食物的盘数与查询的个数。

第二行包含 nn 个整数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n,它是 1,2,⋯ ,n1, 2, \cdots, n 的一个排列,表示第 ii 盘食物有 (ai!)(a_i!) kg,其中 s!=1×2×3×⋯×ss! = 1 \times 2 \times 3 \times \cdots \times s。

第三行包含 mm 个整数,第 ii 个整数 kik_i(1≤ki<t1\leq k_i<t)表示一个查询的重量下限。

输出格式

共 mm 行,每行输出一个整数,表示该查询中 Bob 最少需要选择的连续盘数。如果无法达到 Bob 的目标,输出 -1。

4 2
1 2 3 4
29 31
2
3

提示

翻译由 DeepSeek V4 Pro 完成