F. Optimal Encoding
brute force; data structures
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.
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