CF2030F Orangutan Approved Subarrays

Suppose you have an array $ b $ . Initially, you also have a set $ S $ that contains all distinct elements of $ b $ . The array $ b $ is called orangutan-approved if it can be emptied by repeatedly performing the following operation: - In one operation, select indices $ l $ and $ r $ ( $ 1 \leq l \leq r \leq |b| $ ) such that $ v = b_l = b_{l+1} = \ldots = b_r $ and $ v $ is present in $ S $ . Remove $ v $ from $ S $ , and simultaneously remove all $ b_i $ such that $ l \leq i \leq r $ . Then, reindex the elements $ b_{r+1}, b_{r+2}, \ldots $ as $ b_l, b_{l+1}, \ldots $ accordingly. You are given an array $ a $ of length $ n $ and $ q $ queries. Each query consists of two indices $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ), and you need to determine whether or not the subarray $ a_{l}, a_{l+1}, \ldots, a_r $ is orangutan-approved.

The first line contains $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The first line of each test case contains integers $ n $ and $ q $ ( $ 1 \leq n,q \leq 2 \cdot 10^5 $ ) — the size of $ a $ and the number of queries, respectively. The following line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ) — the elements of the array $ a $ . The following $ q $ lines contain two integers $ l $ and $ r $ — the endpoints of the subarray for each query ( $ 1 \leq l \leq r \leq n $ ). It is guaranteed that the sum of $ n $ and $ q $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each query, output "YES" (without quotes) if the subarray from $ l $ to $ r $ is orangutan-approved, and "NO" (without quotes) otherwise. You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

In the first query of the first testcase, the answer is YES. - Initially, $ S=\{1,2\} $ and $ b=[1,2,2,1] $ - Select $ l=2 $ and $ r=3 $ . Since $ b_2=b_3=2 $ is in $ S $ , we may erase $ b_2 $ and $ b_3 $ from the array, as well as erasing $ 2 $ from $ S $ . The set $ S $ becomes $ \{1\} $ and the array becomes $ [1,1] $ . - Select $ l=1 $ and $ r=2 $ . Since $ b_1=b_2=1 $ is in $ S $ , we may erase $ b_1 $ and $ b_2 $ from the array, as well as erasing $ 1 $ from $ S $ . The set $ S $ becomes $ \{\} $ and the array becomes $ [] $ . - Since the array is now empty, we can say the original array is orangutan-approved. In the first query of the second testcase, the answer is NO, because it can be shown that the subarray $ [2,1,2,1] $ cannot become empty through any sequence of valid operations.