Optimal Encoding

题意翻译

给定 $1 \sim n$ 的排列 $a_1, a_2, \cdots, a_n$ 和 $q$ 个区间 $[l_1, r_1], [l_2, r_2], \cdots, [l_q, r_q]$。定义： - 排列 $b_1, b_2, \cdots, b_n$ 对区间 $[l', r']$ **保序**当且仅当 $\forall l' \leq x < y \leq r'$ 满足 $[a_x < a_y] = [b_x < b_y]$。 - 排列 $b_1, b_2, \cdots, b_n$ 是 **$k \text{-}$相似的**当且仅当 $\{ b_n \}$ 对所有 $[l_i, r_i]$ $(1 \leq i \leq k)$ 保序。 - 一个 DAG 是对 $k \text{-}$相似排列的**编码**，当且仅当其所有拓扑序与所有 $k \text{-}$相似排列一一对应。 对于 $k = 1, 2, \cdots, q$，求对 $k \text{-}$相似排列的编码的最少边数。保证 $n \leq 2.5 \times 10^4, q \leq 10^5$。

题目描述

Touko's favorite sequence of numbers is a permutation $ a_1, a_2, \dots, a_n $ of $ 1, 2, \dots, n $ , and she wants some collection of permutations that are similar to her favorite permutation. She has a collection of $ q $ intervals of the form $ [l_i, r_i] $ with $ 1 \le l_i \le r_i \le n $ . To create permutations that are similar to her favorite permutation, she coined the following definition: - A permutation $ b_1, b_2, \dots, b_n $ allows an interval $ [l', r'] $ to holds its shape if for any pair of integers $ (x, y) $ such that $ l' \le x < y \le r' $ , we have $ b_x < b_y $ if and only if $ a_x < a_y $ . - A permutation $ b_1, b_2, \dots, b_n $ is $ k $ -similar if $ b $ allows all intervals $ [l_i, r_i] $ for all $ 1 \le i \le k $ to hold their shapes. Yuu wants to figure out all $ k $ -similar permutations for Touko, but it turns out this is a very hard task; instead, Yuu will encode the set of all $ k $ -similar permutations with directed acylic graphs (DAG). Yuu also coined the following definitions for herself: - A permutation $ b_1, b_2, \dots, b_n $ satisfies a DAG $ G' $ if for all edge $ u \to v $ in $ G' $ , we must have $ b_u < b_v $ . - A $ k $ -encoding is a DAG $ G_k $ on the set of vertices $ 1, 2, \dots, n $ such that a permutation $ b_1, b_2, \dots, b_n $ satisfies $ G_k $ if and only if $ b $ is $ k $ -similar. Since Yuu is free today, she wants to figure out the minimum number of edges among all $ k $ -encodings for each $ k $ from $ 1 $ to $ q $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n \le 25\,000 $ , $ 1 \le q \le 100\,000 $ ). The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ which form a permutation of $ 1, 2, \dots, n $ . The $ i $ -th of the following $ q $ lines contains two integers $ l_i $ and $ r_i $ . ( $ 1 \le l_i \le r_i \le n $ ).

输出格式

Print $ q $ lines. The $ k $ -th of them should contain a single integer — The minimum number of edges among all $ k $ -encodings.

输入输出样例

输入样例 #1

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

输出样例 #1

2
4
3

输入样例 #2

8 4
3 7 4 8 1 5 2 6
3 6
1 6
3 8
1 8

输出样例 #2

3
5
9
7

输入样例 #3

10 10
10 5 1 2 7 3 9 4 6 8
2 2
4 5
6 8
4 10
4 4
2 7
2 2
7 8
3 7
2 10

输出样例 #3

0
1
3
6
6
9
9
9
9
8

说明

For the first test case: - All $ 1 $ -similar permutations must allow the interval $ [1, 3] $ to hold its shape. Therefore, the set of all $ 1 $ -similar permutations is $ \{[3, 4, 2, 1], [3, 4, 1, 2], [2, 4, 1, 3], [2, 3, 1, 4]\} $ . The optimal encoding of these permutations is  - All $ 2 $ -similar permutations must allow the intervals $ [1, 3] $ and $ [2, 4] $ to hold their shapes. Therefore, the set of all $ 2 $ -similar permutations is $ \{[3, 4, 1, 2], [2, 4, 1, 3]\} $ . The optimal encoding of these permutations is  - All $ 3 $ -similar permutations must allow the intervals $ [1, 3] $ , $ [2, 4] $ , and $ [1, 4] $ to hold their shapes. Therefore, the set of all $ 3 $ -similar permutations only includes $ [2, 4, 1, 3] $ . The optimal encoding of this permutation is