CF2210F A Simple Problem

对于一个长为 $m$ 的数组 $b$，$f(b)$ 的定义如下： - 一个长度为 $m$ 的数组 $c$ 是“美丽的”当且仅当对于所有 $1\le i\le m$，$c_i=\max_{1\le j\le i}\left\{b_j\right\}$ 或 $c_i=\min_{1\le j\le i}\left\{b_j\right\}$。$f(b)$ 被定义为所有“美丽的”数组的最大可能逆序对数量。 给定一个长度为 $n$ 的排列 $p$。有 $q$ 次询问，每次给定 $l,r$，求 $f([p_l,p_{l+1},\dots,p_{r}])$。

输入包含多组测试数据。第一行一个正整数 $t$（$1\le t\le10^4$），表示数据组数。 对于每组数据： \ 第一行两个正整数 $n,q$（$1\le n,q\le10^6$），表示排列 $p$ 的长度和询问次数。 \ 第二行 $n$ 个互不相同的正整数 $p_1,p_2,\dots,p_n$（$1\le p_i\le n$）。 \ 接下来 $q$ 行，每行两个正整数 $l,r$，表示一次查询。 保证 $\sum n,\sum q\le10^6$。

对于每次询问，输出一行一个非负整数表示答案。

在样例第一组数据中： - 对于第二个查询，需要求 $f([1,2])$。取 $c=[\min\left\{1\right\},\min\left\{1,2\right\}]=[1,1]$，其有 $0$ 个逆序对。可以证明这是最大可能值。 在样例第四组数据中： - 对于第三个查询，需要求 $f([3,6,4,9])$。取 $c=[\max\left\{3\right\},\max\left\{3,6\right\},\min\left\{3,6,4\right\},\min\left\{3,6,4,9\right\}]=[3,6,3,3]$，其有 $2$ 个逆序对。可以证明这是最大可能值。