Suppose you have an array 𝑏. Initially, you also have a set 𝑆 that contains all distinct elements of 𝑏. The array 𝑏 is called orangutan-approved if it can be emptied by repeatedly performing the following operation:

In one operation, select indices 𝑙 and 𝑟 (1≤𝑙≤𝑟≤|𝑏|) such that 𝑣=𝑏𝑙=𝑏𝑙+1=…=𝑏𝑟 and 𝑣 is present in 𝑆. Remove 𝑣 from 𝑆, and simultaneously remove all 𝑏𝑖 such that 𝑙≤𝑖≤𝑟. Then, reindex the elements 𝑏𝑟+1,𝑏𝑟+2,… as 𝑏𝑙,𝑏𝑙+1,… accordingly.
You are given an array 𝑎 of length 𝑛 and 𝑞 queries.

Each query consists of two indices 𝑙 and 𝑟 (1≤𝑙≤𝑟≤𝑛), and you need to determine whether or not the subarray 𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟 is orangutan-approved.

Input
The first line contains 𝑡 (1≤𝑡≤104) — the number of test cases.

The first line of each test case contains integers 𝑛 and 𝑞 (1≤𝑛,𝑞≤2⋅105) — the size of 𝑎 and the number of queries, respectively.

The following line contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛) — the elements of the array 𝑎.

The following 𝑞 lines contain two integers 𝑙 and 𝑟 — the endpoints of the subarray for each query (1≤𝑙≤𝑟≤𝑛).

It is guaranteed that the sum of 𝑛 and 𝑞 over all test cases does not exceed 2⋅105.

Output
For each query, output "YES" (without quotes) if the subarray from 𝑙 to 𝑟 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).

Example
inputCopy
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
outputCopy
YES
YES
NO
YES
YES
YES
NO
YES
YES
Note
In the first query of the first testcase, the answer is YES.

Initially, 𝑆={1,2} and 𝑏=[1,2,2,1]
Select 𝑙=2 and 𝑟=3. Since 𝑏2=𝑏3=2 is in 𝑆, we may erase 𝑏2 and 𝑏3 from the array, as well as erasing 2 from 𝑆. The set 𝑆 becomes {1} and the array becomes [1,1].
Select 𝑙=1 and 𝑟=2. Since 𝑏1=𝑏2=1 is in 𝑆, we may erase 𝑏1 and 𝑏2 from the array, as well as erasing 1 from 𝑆. The set 𝑆 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.. You need to optimize the following solution, (it is correct but slow) #include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <string>

using namespace std;

struct Query {
  int l, r, idx;
};
bool mo_cmp(const Query& a, const Query& b, int block_size) {
  int block_a = a.l / block_size;
  int block_b = b.l / block_size;
  if (block_a != block_b) return block_a < block_b;
  return (block_a & 1) ? (a.r < b.r) : (a.r > b.r);
}

void solve() {
  int n, q; cin >> n >> q;
  vector<int> a(n); for (auto &x : a) cin >> x;
  
  vector<vector<int>> pos_map(n + 2, vector<int>());
  for (int i = 0; i < n; ++i) pos_map[a[i]].push_back(i + 1);
  
  vector<Query> queries(q);
  for (int i = 0; i < q; ++i) {
    cin >> queries[i].l >> queries[i].r;
    queries[i].idx = i;
  }
  
  vector<string> answers(q, "NO");
  
  for (int i = 0; i < q; ++i) {
    int l = queries[i].l;
    int r = queries[i].r;
    
    vector<pair<int, int>> elements;
    
    for (int val = 1; val <= n; ++val) {
      if (pos_map[val].empty()) continue;
      int first_idx = lower_bound(pos_map[val].begin(), pos_map[val].end(), l) - pos_map[val].begin();
      if (first_idx == pos_map[val].size()) continue;
      int first = pos_map[val][first_idx];
      if (first > r) continue;
      int last_idx = upper_bound(pos_map[val].begin(), pos_map[val].end(), r) - pos_map[val].begin() - 1;
      if (last_idx < 0) continue;
      int last = pos_map[val][last_idx];
      if (last < l) continue;
      elements.emplace_back(first, last);
    }
    
    sort(elements.begin(), elements.end());
    
    bool ok = true;
    int current_max = 0;
    for (auto &[first, last] : elements) {
      if (first > current_max) {
        current_max = last;
      } else {
        if (last <= current_max) {
          current_max = max(current_max, last);
        } else {
          ok = false;
          break;
        }
      }
    }
    
    if (ok) answers[queries[i].idx] = "YES";
    else answers[queries[i].idx] = "NO";
    
  }
  
  for (auto &ans : answers) cout << ans << "\n";
  
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int t; cin >> t;
  while (t--) solve();
  
}