## USACO 2021 February Contest, Platinum

## Problem 1. No Time to Dry

Contest has ended.

**Log in to allow submissions in analysis mode**

Initially, all fence segments are uncolored. Bessie can color any contiguous range of segments with a single color in a single brush stroke as long as she never paints a lighter color over a darker color (she can only paint darker colors over lighter colors).

For example, an initially uncolored segment of length four can be colored as follows:

0000 -> 1110 -> 1122 -> 1332

Unfortunately, Bessie doesn't have time to waste watching paint dry. Thus, Bessie thinks she may need to leave some fence segments unpainted! Currently, she is considering $Q$ candidate ranges ($1\le Q\le 2\cdot 10^5$), each described by two integers $(a,b)$ with $1 \leq a \leq b \leq N$ giving the indices of endpoints of the range $a \ldots b$ of segments to be painted.

For each candidate range, what is the minimum number of strokes needed to paint every fence segment inside the range with its desired color while leaving all fence segments outside the range uncolored? Note that Bessie does not actually do any painting during this process, so the answers for each candidate range are independent.

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$ and $Q$.The next line contains an array of $N$ integers representing the desired color for each fence segment.

The next $Q$ lines each contain two space-separated integers $a$ and $b$ representing a candidate range to possibly paint.

#### OUTPUT FORMAT (print output to the terminal / stdout):

For each of the $Q$ candidates, output the answer on a new line.#### SAMPLE INPUT:

8 4 1 2 2 1 1 2 3 2 4 6 3 6 1 6 5 8

#### SAMPLE OUTPUT:

2 3 3 3

In this example, the sub-range corresponding to the desired pattern

1 1 2

requires two strokes to paint. The sub-range corresponding to the desired pattern

2 1 1 2

requires three strokes to paint. The sub-range corresponding to the desired pattern

1 2 2 1 1 2

requires three strokes to paint. The sub-range corresponding to the desired pattern

1 2 3 2

requires three strokes to paint.

#### SCORING:

- Test cases 1-2 satisfy $N,Q\le 100$.
- Test cases 3-5 satisfy $N,Q\le 5000$.
- In test cases 6-10, the input array contains no integer greater than $10$.
- Test cases 11-20 satisfy no additional constraints.

Problem credits: Andi Qu, Brian Dean, and Benjamin Qi