LowbieH and his friend wtd are on their trip to the SUSTech natural park. The place is quite mountainous and they can climb \(n\) mountains lying on a straight line numbered from \(1\) to \(n\), each with height \(h_i(1 \leq i \leq n)\). To save time, they decide to climb two different mountains and they want to see each other when they reach the top. That is to say, LowbieH will choose the \(i_{th}\) mountain and wtd will climb the \(j_{th}\) mountain\((1 \leq i < j \leq n)\). For the \(k_{th}(i < k < j)\) moutain that is between their choices, it should satisfy that \(h_k < min(h_i,\ h_j)\). Thus no moutains will block cross their visions. Also, if LowbieH and wtd are on the adjacent mountains, they can certainly see each other.

Now we define such pair of mountains \((i,\ j)\) to be a happy pair if LowbieH and wtd can see each other on them. Can you tell them the number of all different happy pairs within given intervals ?

The first line of input contains two integers \(n,\ q\ (1 \leq n,\ q \leq 3*10^5)\), which means the number of moutains and queries.

The second line of input contains \(n\) integers \(h_1, \cdots, h_n\ (1 \leq h_i \leq 10^9)\), denoting the height of each moutain.

The following \(q\) lines contain two integers \(l,\ r\ (1 \leq l \leq r \leq n)\) in each line, which means that the interval of query is \([l,\ r]\). You should calculate the number of different happy pairs within this interval.

The output will be \(q\) lines in total. Each line contains the answer of each query.

You are recommended to use fast I/O.