시간 제한메모리 제한제출정답맞은 사람정답 비율
7 초 512 MB111100.000%

문제

Zoran is a Zookeeper at the Zagreb Zoo. He is currently conducting scientific research on the relationship between visitor satisfaction and the way animals are presented throughout the zoo.

A visitor’s walk through the entire zoo can be viewed as a sequence of $N$ habitats each containing a certain species of animal. The $i$-th habitat initially contains animals of species $a_i$, and visitors are expected to observe the habitats in order.

Zoran started experimenting with the order in which the animals were presented. He then proceeded to ask questions about visitor satisfaction during their visit. It turned out that the visitors are most satisfied when the total diversity of their walk is as small as possible.

Here, the diversity of a sequence of habitats is defined as the number of different animal species one can observe in these habitats, whereas the total diversity of a sequence of habitats is defined as the sum of diversities over all of its contiguous subsequences.

For example, the diversity of a sequence (1, 1, 2) is 2 because there are two distinct animal species in that sequence. Meanwhile, the total diversity of that sequence is 8 because its contiguous subsequences (1), (1), (2), (1, 1), (1, 2) and (1, 1, 2) have diversities equal to 1, 1, 1, 1, 2 and 2 respectively.

Zoran knows which animal species currently occupies which habitat. Before he reorganizes the zoo, he would like you to answer $Q$ independent queries. In the $i$-th query, he wants to know the smallest possible total diversity of the contiguous subsequence starting from the $l_i$-th and ending at the $r_i$-th habitat that he can achieve by reordering the animals living in these habitats.

입력

The first line contains two integers $N$ and $Q$ from the task description.

The second line contains $N$ space-separated integers $a_1$, $a_2$, ..., $a_N$. The $i$-th of these integers represents the animal species occupying the $i$-th habitat.

Each of the next $Q$ lines contains two integers $l_i$ and $r_i$ ($1 ≤ l_i \le r_i \le N$) describing a single query.

Note that all queries are independent of each other, i.e. you should answer them under the assumption that the $i$-th habitat is initially occupied by the animal species $a_i$.

출력

The $i$-th line of output should contain a single integer representing the answer to the $i$-th query.

서브태스크

번호 배점 제한
1 4

$1 \le N \le 11$, $1 \le a_i \le 300\,000$, $Q = 1$, $l_1 = 1$, $r_1 = N$

2 10

$1 \le N \le 300\,000$, $1 \le a_i \le 11$, $Q = 1$, $l_1 = 1$, $r_1 = N$

3 8

$1 \le N \le 300\,000$, $1 \le a_i \le 23$, $Q = 1$, $l_1 = 1$, $r_1 = N$

4 16

$1 \le N \le 300\,000$, $1 \le a_i \le 1\,000$, $Q = 1$, $l_1 = 1$, $r_1 = N$

5 26

$1 \le N \le 300\,000$, $1 \le a_i \le 300\,000$, $Q = 1$, $l_1 = 1$, $r_1 = N$

6 36

$1 \le N \le 300\,000$, $1 \le a_i \le 300\,000$, $1 \le Q \le 50\,000$

예제 입력 1

3 1
1 2 3
1 3

예제 출력 1

10

In any ordering, the diversity of every contiguous subsequence is equal to the number of its elements. Hence, the answer to the query is 1 + 1 + 1 + 2 + 2 + 3 = 10.

예제 입력 2

4 2
1 1 1 1
1 2
2 4

예제 출력 2

3
6

In any ordering, every contiguous subsequence has diversity equal to 1. Thus, for each query, the answer is the number of contiguous subsequences contained in the given contiguous subsequence.

예제 입력 3

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

예제 출력 3

16
8
4

In the first query, an optimal ordering is (1, 2, 2, 3), which has total diversity equal to 1 + 1 + 1 + 1 + 2 + 1 + 2 + 2 + 2 + 3 = 16. In the second query, an optimal ordering is (1, 1, 2), which has total diversity equal to 1 + 1 + 1 + 1 + 2 + 2 = 8. In the third query, an optimal ordering is (1, 3), which has total diversity equal to 1 + 1 + 2 = 4.

채점 및 기타 정보

  • 예제는 채점하지 않는다.