暂无测试数据。

$\text{Mila}$ 最近学习了两个新的魔法，她迫不及待地想要尝试一下。

这两种魔法是作用在魔法序列上的，两种魔法分别为：

1. 使一个区间内所有数 $-1$​，魔力消耗为区间长度。
2. 使一个区间内所有数变成 $0$，魔力消耗为区间内所有数的乘积。

$\text{Mila}$ 有 $q$ 次询问，每次询问给出一个区间 $[l,r]$，由于 $\text{Mila}$ 不想耗费太多魔力，她想要知道：通过上面两种操作，将这个区间内所有数变成 $0$ 的最小魔力消耗——并且操作过程中区间内的数不能为负数。

输入格式

第一行两个整数 $n,q$，表示魔法序列长度和询问次数。

第二行 $n$ 个整数表示该魔法序列。

下面 $q$ 行，每行两个整数 $l,r$，表示一次对区间 $[l,r]$ 的询问。注意，询问之间两两互不影响，即一次询问的操作并不会真实地操作出来，因为 $\text{Mila}$ 只是想要知道，而不打算实践。

输出格式

输出 $q$ 行，每行一个整数表示最小魔力消耗。

数据规模与约定

对于前 $20\%$ 的数据，满足 $a_i,n\leq 10,q\leq 10$。

对于前 $40\%$ 的数据，满足 $n\leq 10^3,q\leq 10^3$

对于另外 $20\%$ 的数据，满足 $a_i=1$。

对于 $100\%$ 的数据，满足 $1\leq n\leq 10^6,1\leq q\leq 10^6,1\leq a_i\leq 10^9$。

3 1
1 1 1
1 3

1