U360645 小 C 的大冒险

随着一声巨响，种子从土里破芽而出，并且以惊人的速度向上生长，很快，这粒种子就长成了一颗参天巨树，小 C 吃惊地看着哆啦 B 梦，小哆啦表示竹蜻蜓已经坏了，现在只能靠我们自己爬上去了。 但是很明显，这颗巨树的叶子是具有一定的规律的，必须要解开这颗巨树的秘密才能安全地规划路线，爬上巨树之巅。 很明显，这时静夫希望你能出手，毕竟小 C 肯定不会。 随着谜题的解开，老人给了小 C 一粒种子，便慢慢离去了。看着老人的背影，小 C 种下了这颗种子。 随着一声巨响，种子从土里破芽而出，并且以惊人的速度向上生长，很快，这粒种子就长成了一颗参天巨树，小 C 吃惊地看着哆啦 B 梦，小哆啦表示竹蜻蜓已经坏了，现在只能靠我们自己爬上去了。 但是很明显，这颗巨树的叶子是具有一定的规律的，必须要解开这颗巨树的秘密才能安全地规划路线，爬上巨树之巅。 很明显，这时静夫希望你能出手，毕竟小 C 肯定不会。

首先巨树的每个枝干有三片叶子，但是他们太杂乱无章了，组成了一片叶林，哆啦把每片叶子抽象成了一个数字，这样的话你会得到一个序列，对于这个序列，你要从中找到三个数 $a_{i}，a_{j}，a_{k}$，满足对于所有 $1≤i

第 $1$ 行是两个数字 $n，q$，代表序列的长度,和询问的次数。 第 $2$ 行是一个长度为 $n$ 的序列。 接下来 $q$ 行，每行两个数字，$l,r$。

$q$ 行，每行一个整数，表示所有的组合方案数。

对于 $20$% 的数据，$1≤n≤100，1≤q≤100，1≤a_{i}≤n$。 对于 $40$% 的数据，$1≤n≤1000，1≤q≤100，1≤a_{i}≤n$。 对于 $60$% 的数据，$1≤n≤10000，1≤q≤10000，1≤a_{i}≤n$。 对于 $100$% 的数据，$1≤n≤2\times10^5，1≤q≤2\times10^5，1≤a_{i}≤n$。 ## [题解](https://www.luogu.com.cn/blog/liuyccc/xiao-c-di-tai-mao-xian-ti-xie)