Вы играете в головоломку, в которой участвуют $n$ драгоценных камней, выстроенных в ряд и пронумерованных от $1$ до $n$ слева направо. $i$-й драгоценный камень имеет цвет $c[i]$.
В любой момент вы можете выбрать два соседних драгоценных камня одинакового цвета и удалить их. После этого камни, находившиеся по обе стороны от удаленных, сдвигаются, закрывая промежуток, что может привести к образованию новых соседних пар одинакового цвета.
Вам будет предложено $q$ независимых сценариев. В $j$-м сценарии рассматриваются только камни, начиная с камня $l[j]$ и заканчивая камнем $r[j]$. Предполагая, что вы выполняете оптимальную последовательность удалений, какое минимальное количество драгоценных камней может остаться?
Входные данные
Ваша программа должна считывать данные из стандартного потока ввода.
Первая строка входных данных содержит два целых числа $n$ и $q$, разделенных пробелом.
Вторая строка содержит $n$ целых чисел $c[1], c[2], \dots, c[n]$, разделенных пробелами.
Следующие $q$ строк содержат по два целых числа, разделенных пробелом. $i$-я из этих строк содержит $l[i]$ и $r[i]$.
Выходные данные
Ваша программа должна выводить данные в стандартный поток вывода.
Выходные данные должны содержать $q$ строк. $i$-я строка должна содержать одно целое число — ответ для $i$-го сценария.
Ограничения
Для всех тестовых случаев входные данные удовлетворяют следующим условиям:
- $1 \le n \le 10^6$
- $1 \le q \le 500\,000$
- $1 \le c[i] \le 10^9$ для всех $1 \le i \le n$
- $1 \le l[j] \le r[j] \le n$ для всех $1 \le j \le q$
Подзадачи
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 0 | 0 | Примеры тестов |
| 1 | 2 | $c[1] = c[2] = \dots = c[n]$ |
| 2 | 5 | Драгоценные камни одного цвета образуют непрерывный подмассив (если $c[i] = c[j]$ и $i < j$, то $c[i] = c[i + 1] = \dots = c[j]$) |
| 3 | 9 | $n, q \le 2000$ |
| 4 | 4 | $l[j] = 1$ для всех $1 \le j \le q$ |
| 5 | 8 | Ровно два драгоценных камня каждого цвета |
| 6 | 16 | $c[i] \le 2$ для всех $1 \le i \le n$ |
| 7 | 18 | $n, q \le 100\,000$ |
| 8 | 15 | $n, q \le 300\,000$ |
| 9 | 23 | Нет дополнительных ограничений |
Примеры
Входные данные 1
8 4 3 3 3 2 2 3 4 7 1 3 3 6 1 7 5 8
Выходные данные 1
1 0 1 4
Примечание
Пояснение к примеру 1: $n = 8$ драгоценных камней показаны на схеме ниже.
В первом сценарии рассматриваются только первые три камня. Удаление любых двух соседних камней оставит ровно один, после чего удаление станет невозможным. Следовательно, ответ — 1.
Во втором сценарии камни могут быть удалены следующим образом, не оставив ни одного:
В третьем сценарии камни могут быть удалены следующим образом, оставив один:
В четвертом сценарии никакие камни не могут быть удалены. Следовательно, ответ — 4.
Входные данные 2
6 3 2 1 1 2 2 1 1 6 1 4 3 6
Выходные данные 2
2 0 0