不知道怎么回事，Leohh用来写复习笔记的活页本被弄乱了，页码乱七八糟。但是Leohh偶然发现按照这样的顺序，连续复习中间的某些笔记，可以起到随机抽检巩固记忆的效果。
具体来说，复习笔记总共有 页，现在从前往后的页码分别为 ，是一个 的排列。复习 这些页的复习效果等于二元组 的个数，其中 满足 且 。
现在有 个询问，第 个询问给定 ，问你复习 这些页的复习效果是多少。
第一行两个整数 ，表示总页数和询问数
第二行 个整数，表示从前往后的页码
接下来 行，每行两个整数 ，表示询问的范围
共 行，对于每次询问，输出复习效果的值
8 4 3 5 4 1 2 7 6 8 1 4 2 6 5 8 1 8
7 10 6 20