Minimum Brush Strokes

Bessie recently received a set of paints and wants to color one end of her pasture's fence. The fence consists of $N$ segments, each $1$ meter long ($1\le N\le 2\cdot10^5$). Bessie has $N$ different colors, labeled from $1$ (lightest) to $N$ (darkest), so that her desired painting can be described by an array of $N$ integers.

Initially, all segments are uncolored (denoted by $0$). In one stroke, Bessie can paint any contiguous sequence of segments with a single color, under the restriction that she is not allowed to paint a lighter color over a darker one (i.e. she can only use a darker color to cover a lighter one).

For example, a $4$-segment fence that starts uncolored (represented as "0000") can be painted as follows:

0000 -> 1110 -> 1122 -> 1332

Unfortunately, due to the drying time, Bessie may need to give up painting some segments. She is now considering $Q$ candidate intervals ($1\le Q\le 2\cdot10^5$), where each interval is represented by two integers $(a,b)$ such that $1\le a\le b\le N$. In each candidate interval, only the fence segments from position $a$ to $b$ will be painted with their desired colors, and the segments outside will remain uncolored.

Your task is to determine the minimum number of painting strokes required for each candidate interval. Each query is independent.

inputFormat

The first line contains two integers $N$ and $Q$. The second line contains $N$ integers, representing the desired colors for each fence segment. Each of the next $Q$ lines contains two integers $a$ and $b$, representing a candidate interval.

outputFormat

For each query, output a single integer representing the minimum number of strokes required to paint the specified interval.

sample

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

3
1
1
2