markdown

G. 递归查询

时间限制：每个测试点 $4$ 秒
内存限制：每个测试点 $256$ MB
输入：标准输入
输出：标准输出

题目描述

给定一个 $1$ 到 $n$ 的排列 $p_1, p_2, \dots, p_n$。你需要回答 $q$ 个查询。每个查询是一个数对 $(l_i, r_i)$，你需要计算 $f(l_i, r_i)$。

定义 $m(l, r)$ 为子段 $p_l, p_{l+1}, \dots, p_r$ 中最大值所在的位置。
那么

$$f(l, r) = \begin{cases} (r - l + 1) + f(l, m(l, r) - 1) + f(m(l, r) + 1, r) & \text{若 } l \le r \\ 0 & \text{否则} \end{cases} $$

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 10^6$，$1 \le q \le 10^6$）—— 排列的大小和查询的数量。
第二行包含 $n$ 个两两不同的整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$，且当 $i \ne j$ 时 $p_i \ne p_j$）—— 给定的排列。
第三行包含 $q$ 个整数 $l_1, l_2, \dots, l_q$ —— 每个查询的左端点。
第四行包含 $q$ 个整数 $r_1, r_2, \dots, r_q$ —— 每个查询的右端点。
数据保证对于所有查询，有 $1 \le l_i \le r_i \le n$。

输出格式

输出 $q$ 个整数 —— 每个查询对应的 $f(l_i, r_i)$ 的值。

样例

输入

4 5
3 1 4 2
2 1 1 2 1
2 3 4 4 1

输出

1 6 8 5 1

样例解释

各查询的计算过程如下：

• $f(2,2) = (2-2+1) + f(2,1) + f(3,2) = 1 + 0 + 0 = 1$
• $f(1,3) = (3-1+1) + f(1,2) + f(4,3) = 3 + (2-1+1) + f(1,0) + f(2,2) = 3 + 2 + (2-2+1) = 6$
• $f(1,4) = (4-1+1) + f(1,2) + f(4,4) = 4 + 3 + 1 = 8$
• $f(2,4) = (4-2+1) + f(2,2) + f(4,4) = 3 + 1 + 1 = 5$
• $f(1,1) = (1-1+1) + 0 + 0 = 1$