Предположим, у вас есть массив \(b\). Изначально у вас также есть множество \(S\), которое содержит все различные элементы массива \(b\). Массив \(b\) называется орангутано-одобренным, если его можно сделать пустым, выполняя следующую операцию:
- Выбрать индексы \(l\) и \(r\) (\(1 \leq l \leq r \leq |b|\)) такие, что \(v = b_l = b_{l+1} = \ldots = b_r\) и \(v\) присутствует в \(S\). Удалить \(v\) из \(S\), а также удалить все \(b_i\), для которых \(l \leq i \leq r\). Затем подвинуть элементы \(b_{r+1}, b_{r+2}, \ldots\) влево на позиции \(b_l, b_{l+1}, \ldots\) соответственно.
Вам дан массив \(a\) длины \(n\) и \(q\) запросов.
Каждый запрос состоит из двух индексов \(l\) и \(r\) (\(1 \le l \le r \le n\)), и вам нужно определить, является ли подмассив \(a_{l}, a_{l+1}, \ldots, a_r\) орангутано-одобренным.
Выходные данные
Для каждого запроса выведите «YES» (без кавычек), если подмассив от \(l\) до \(r\) является орангутано-одобренным, и «NO» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом запросе первого набора входных данных ответ — YES.
- Изначально \(S=\{1,2\}\) и \(b=[1,2,2,1]\).
- Выберите \(l=2\) и \(r=3\). Поскольку \(b_2=b_3=2\) находится в \(S\), мы можем удалить \(b_2\) и \(b_3\) из массива, а также удалить \(2\) из \(S\). Множество \(S\) становится \(\{1\}\), а массив — \([1,1]\).
- Выберите \(l=1\) и \(r=2\). Поскольку \(b_1=b_2=1\) находится в \(S\), мы можем удалить \(b_1\) и \(b_2\) из массива, а также удалить \(1\) из \(S\). Множество \(S\) становится \(\{\}\), а массив — \([]\).
- Поскольку массив теперь пуст, мы можем сказать, что исходный массив — орангутано-одобренный
В первом запросе второго набора входных данных ответ — NO, потому что можно показать, что подмассив \([2,1,2,1]\) не может стать пустым ни при какой последовательности корректных операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 2
1 2 2 1
1 4
1 3
5 3
1 2 1 2 1
2 5
3 5
1 3
8 4
1 2 3 2 1 3 2 3
1 5
2 8
3 5
6 8
|
YES
YES
NO
YES
YES
YES
NO
YES
YES
|