## KDOMINO - K-dominant array

no tags

Professor Mahammad was sitting in his garden when an apple fell on his head, and in a stroke of brilliant insight, he suddenly came up with K-dominant notation. An array with length L is called K-dominant, if and only if there is at least one element x lying in the array for which occurrence(x) * K >= L. After analyzing several arrays with this property, professor now, made up a new problem for you. Your task is simple, there are given an array of length N and several queries. For each of the queries, you just need to check whether the subarray [l, r] is k-dominant or not.

### Input

The first line of the input contains two positive integers N and Q, the number of elements of the array and the mean, respectively. (N, Q ≤ 200000).

The following line contains N integers which represent elements of the array.

The following Q lines contains three integers lr, and k. (1 ≤ l ≤ r ≤ N).

All the numbers in the input section are 32-bit positive integers.

Sum of all k's in queries does not exceed 500000.

### Output

For each of the queries, print per line YES or NO if there is an element lying in the subarray which satisfies the condition in the statement.

### Example

```Input:
8 3
1 4 2 3 2 2 5 3
2 6 2
1 8 2
1 8 3

Output:
YES
NO
YES```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);

const int N = 2e5+5;
const int M = 2e5+5;
const int SQN = sqrt(N) + 1;

struct query{
int l, r;
int idx;
int block;
int k;
query(){}
query(int _l, int _r, int _k, int _id){
l = _l;
r = _r;
k = _k;
block = _l/SQN;
idx = _id;
}
bool operator < (const query &b) const{
if(block != b.block)
return block < b.block;
return r < b.r;
}

};

query Q[M];
int ans[M];
int n, q;
int arr[N], temp[N];
int freq[N], counter[N];

int main(){
scanf("%d%d", &n, &q);
for(int i = 1;i <= n; i++){
scanf("%d", arr+i);
temp[i] = arr[i];
}
sort(temp + 1, temp + 1 + n);
for(int i = 1;i <= n; i++){
int id = lower_bound(temp+1, temp+1+n, arr[i]) - (temp+1);
arr[i] = id+1;
}
for(int i = 1;i <= q; i++){
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
Q[i] = query(l, r, k, i);
}
sort(Q+1, Q+1+q);
int curl = 1, curr = 0;
int t_ans = 0;
for(int i = 1;i <= q; i++){
int l = Q[i].l;
int r = Q[i].r;
int idx = Q[i].idx;
int k = Q[i].k;
while(curr < r){
++curr;
int val = arr[curr];
int c = freq[val];
counter[c]--;
freq[val]++;
counter[freq[val]]++;
t_ans = max(t_ans, freq[val]);
}
while(curl > l){
--curl;
int val = arr[curl];
int c = freq[val];
counter[c]--;
freq[val]++;
counter[freq[val]]++;
t_ans = max(t_ans, freq[val]);
}
while(curr > r){
int val = arr[curr];
int c = freq[val];
counter[c]--;
freq[val]--;
counter[freq[val]]++;
while(counter[t_ans] == 0)	t_ans--;
--curr;
}
while(curl < l){
int val = arr[curl];
counter[freq[val]]--;
freq[val]--;
counter[freq[val]]++;
while(counter[t_ans] == 0)	t_ans--;
++curl;
}
if(t_ans*k >= (r-l+1))
ans[idx] = 1;
}
for(int i = 1;i <= q; i++){
printf("%s\n", (ans[i] == 1) ? "YES" : "NO");
}
return 0;
}``````
Copy The Code &

Input

cmd
8 3
1 4 2 3 2 2 5 3
2 6 2
1 8 2
1 8 3

Output

cmd
YES
NO
YES