## DQUERY - D-query

Given a sequence of n numbers a1, a2, ..., an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, ..., aj.

### Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 106).
• Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
• In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

### Output

• For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, ..., aj in a single line.

```Input
5
1 1 2 1 3
3
1 5
2 4
3 5

Output
3
2
3 ```

## 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);
#define M_PI                3.14159265358979323846

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

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

int n, q;

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

int arr[N];
query Q[M];
int print[M];
int cnt[1000005];

int main(){
scanf("%d", &n);
for(int i = 1;i <= n; i++){
scanf("%d", arr+i);
}
cin >> q;
for(int i = 1;i <= q; i++){
int l, r;
scanf("%d%d", &l, &r);
Q[i] = query(l, r, i);
}
sort(Q+1, Q+1+q);
int curl = 1, curr = 0;
ll ans = 0;
for(int i = 1;i <= q; i++){
int l = Q[i].l;
int r = Q[i].r;
int id = Q[i].idx;
while(curr < r){
++curr;
cnt[arr[curr]]++;
if(cnt[arr[curr]] == 1>
ans++;
}
while(curl > l){
--curl;
cnt[arr[curl]]++;
if(cnt[arr[curl]] == 1)
ans++;
}
while(curr > r){
cnt[arr[curr]]--;
if(cnt[arr[curr]] == 0)
ans--;
--curr;
}
while(curl < l){
cnt[arr[curl]]--;
if(cnt[arr[curl]] == 0)
ans--;
++curl;
}
print[id] = ans;
}
for(int i = 1; i <= q; i++)
printf("%d\n", print[i]);
return 0;
}``````
Copy The Code &

Input

cmd
5
1 1 2 1 3
3
1 5
2 4
3 5

Output

cmd
3
2
3

### #2 Code Example with Java Programming

```Code - Java Programming```

``````import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;

/**
* Created by sreps on 7/31/2016.
*/
public class DQUERY {

static Integer input[];
static HashMap < Integer, Integer> count;

public static void main(String[] args) throws IOException {

input = new Integer[N + 1];
count = new HashMap < >();

for (int i = 1; i <= N; i++) {
input[i] = Integer.parseInt(temp[i - 1]);
}

ArrayList<Query> queries = new ArrayList<>();
for (int i = 0; i < Q; i++) {
Integer left = Integer.parseInt(temp[0]);
Integer right = Integer.parseInt(temp[1]);
}

int currentLeft = 1, currentRight = 1;
for (Query query : queries) {
int left = query.left;
int right = query.right;

while (left < currentLeft) {
currentLeft--;
}
while (left > currentLeft) {
removal(left);
left--;
}
while (right < currentRight) {
right++;
}
while (right > currentRight) {
removal(right);
right--;
}

currentLeft = query.left;
currentRight = query.right;
}
}

static class Query {
public Integer left;
public Integer right;

Query(Integer left, Integer right) {
this.left = left;
this.right = right;
}
}

public static void addition(int position) {
Integer current = count.get(input[position]);
if (current == null) {
count.put(input[position], 1);
return;
}
if (current == 0) {
current = 0;
}
count.put(input[position], current + 1);
}

public static void removal(int position) {
Integer current = count.get(input[position]);
if (current == null) {
return;
}
if (current == 1) {
}
count.put(input[position], current - 1);
}
}``````
Copy The Code &

Input

cmd
5
1 1 2 1 3
3
1 5
2 4
3 5

Output

cmd
3
2
3