P11573 [COTS 2015] 关灯泡 / Žarulje

译自 [Izborne Pripreme 2015 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/prip15/) D1T2。$\texttt{1s,0.5G}$。

有 $n$ 盏灯泡排成一排，从左到右编号 $1\sim n$。第 $i$ 盏灯泡发光的功率为 $a_i$ 瓦。 现在想要将所有灯泡全部关闭。考虑如下的贪心算法： - 选择起始位置 $p$。关闭灯泡 $p$。 - 令当前位置为 $x$。若还有灯泡未关闭，循环执行以下流程： - 若只有 $x$ 左边有未关闭的灯泡，则关闭 $x$ 左边离 $x$ 最近的灯泡 $l$，并令 $x\gets l$。 - 若只有 $x$ 右边有未关闭的灯泡，则关闭 $x$ 右边离 $x$ 最近的灯泡 $r$，并令 $x\gets r$。 - 否则，$x$ 左边离 $x$ 最近的灯泡为 $l$，令 $x$ 右边离 $x$ 最近的灯泡为 $r$。 - 如果两盏灯泡功率相等，则随机选择一盏灯泡 $y$。关闭 $y$，并令 $x\gets y$。 - 否则，令功率更大的灯泡为 $y$。关闭 $y$，并令 $x\gets y$。 定义 $f(p)$ 为起始位置为 $p$ 时，上述贪心算法产生的不同关灯泡序列有多少个。 给定 $m$ 个位置 $x_1,x_2,\cdots,x_m$。对于 $i=1,2,\cdots,m$，求出 $f(x_i)$ 对 $(10^9+7)$ 取模后的结果。

第一行，两个正整数 $n,m$。 第二行，$n$ 个正整数 $a_1,a_2,\cdots,a_n$。 第三行，$m$ 个正整数 $x_1,x_2,\cdots,x_m$。

输出 $m$ 行。每行一个整数，表示答案对 $(10^9+7)$ 取模后的结果。

#### 样例解释 样例 $1$ 解释：起始位置为 $3$ 时，$[3,2,4,1,5]$ 和 $[3,2,4,5,1]$ 是可能的两种关灯泡顺序。 #### 数据范围 对于 $100\%$ 的数据，保证： - $1\le x_i\le n\le 2\times 10^5$； - $1\le a_i,m\le 2\times 10^5$。 | 子任务编号 | $n\le $ | $m\le $ | 得分 | | :--: | :--: | :--: | :--: | | $ 1 $ | $ 2\times 10^3 $ | $2\times 10^3$ |$ 22 $ | | $ 2 $ | $ 2\times 10^5 $ | $ 5 $ | $ 38 $ | | $ 3 $ | $ 2\times 10^5 $ | $ 2\times 10^5 $ | $ 40 $ |