有一个长度为 nnn 的序列和 qqq 次询问，每次询问序列中有多少区间（不包括 [l,r][l,r][l,r] ）的最大值等于区间 [l,r][l,r][l,r] 的最大值。
第一行两个正整数 n,q(1≤n,q≤100000)n,q(1\leq n,q\leq 100000)n,q(1≤n,q≤100000)。
第二行 nnn 个正整数 ai(1≤ai≤n)a_i(1\leq a_i\leq n)ai(1≤ai≤n) 表示序列。
接下来 qqq 行每行两个正整数 l,r(1≤l≤r≤n)l,r(1\le l\le r\le n)l,r(1≤l≤r≤n)。
qqq 行，表示每组询问的答案。
样例输入:
8 3 1 4 7 7 4 4 1 1 3 4 5 8 1 1
样例输出:
22 8 3
