Назовём массив $$$b_1,b_2,\ldots,b_{2k-1}$$$, $$$k$$$-древесным, для целого $$$k \geq 2$$$, если его элементы можно переставить таким образом, чтобы одновременно были выполнены следующие условия:
- $$$b_1 = k$$$
- Если рассмотреть граф, в котором есть вершины, соответствующие всем различным значениям среди $$$b_2, b_3, \ldots, b_{2k-1}$$$, и провести в нём $$$k-1$$$ рёбер между вершинами с значениями $$$b_2$$$ и $$$b_3$$$, $$$b_4$$$ и $$$b_5$$$, ..., $$$b_{2k-2}$$$ и $$$b_{2k-1}$$$, то получившийся граф должен быть деревом$$$^{\text{∗}}$$$
Более неформально, после перестановки массив должен представлять собой то, как чаще всего задаётся в входных данных дерево размера $$$k$$$: первым элементом является $$$k$$$, количество вершин, а далее задаётся $$$k-1$$$ рёбер, и каждое ребро задаётся двумя вершинами. Обратите внимание, что номерами вершин могут быть любые целые числа.
Например, массив $$$[4, 100, 4, 3, 3]$$$ является $$$3$$$-древесным, так как его элементы можно переставить в $$$[3, 3, 4, 4, 100]$$$, и граф с рёбрами $$$3 \leftrightarrow 4$$$, $$$4 \leftrightarrow 100$$$ является деревом из $$$3$$$ вершин.
Вам дан массив $$$a_1, a_2, \ldots, a_n$$$ и $$$q$$$ запросов. В каждом запросе даны два числа $$$1 \leq l \leq r \leq n$$$, и нужно найти количество целых $$$k \geq 2$$$ таких, что у массива $$$a_l, \ldots, a_r$$$ есть хотя бы одна $$$k$$$-древесная подпоследовательность.
$$$^{\text{∗}}$$$Напомним, что граф на $$$k$$$ вершинах является деревом, если он является связным, то есть между каждой парой вершин существует путь по рёбрам графа, и содержит ровно $$$k-1$$$ рёбер. В частности, дерево не содержит петель и кратных рёбер.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n, q$$$ ($$$1 \le n \le 10^5, 1 \le q \le 10^5$$$) — длина массива и количество запросов.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2n$$$) — массив $$$a$$$.
Каждая из последующих $$$q$$$ строк набора входных данных содержит два целых числа $$$l, r$$$ ($$$1 \le l \le r \le n$$$) — параметры запроса.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$, а также сумма $$$q$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Выведите ответ на каждый запрос в отдельной строке.
110 156 1 13 6 4 4 1 5 2 51 101 92 101 82 93 101 72 83 94 101 62 73 84 95 10
3 3 2 1 1 1 1 0 1 1 0 0 0 1 1
В первом тестовом примере, в первом запросе существуют следующие древесные подпоследовательности:
- $$$2$$$-древесная подпоследовательность $$$[6, 4, 2]$$$. Элементы этого массива можно переставить в $$$[2, 4, 6]$$$ и получить дерево.
- $$$4$$$-древесная подпоследовательность $$$[1, 4, 4, 1, 5, 2, 5]$$$. Элементы этого массива можно переставить в $$$[4, 4, 5, 5, 1, 1, 2]$$$ и получить дерево.
- $$$5$$$-древесная подпоследовательность $$$[6, 1, 13, 6, 4, 4, 1, 2, 5]$$$. Элементы этого массива можно переставить в $$$[5, 2, 1, 1, 6, 6, 4, 4, 13]$$$ и получить дерево.
Эти три дерева представлены на картинках ниже.
