B"Touko's favorite sequence of numbers is a permutation a_1, a_2, ... , a_n of 1, 2, ... , 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 <= l_i <= r_i <= n . To create permutations that are similar to her favorite permutation, she coined the following definition: 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: 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 <= n <= 25 ,000 , 1 <= q <= 100 ,000 ). The second line contains n integers a_1, a_2, ... , a_n which form a permutation of 1, 2, ... , n . The i -th of the following q lines contains two integers l_i and r_i . ( 1 <= l_i <= r_i <= 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: "...