A14234 | Optimal Encoding

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.