#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn =  + ;

struct Node {

    int L, R;

    int sum;

} seg[maxn << ];

int T[maxn];

int tot;

int build(int L, int R) {

    int root = ++tot;

    seg[root].sum = ;

    if (L < R) {

        int mid = (L + R) >> ;

        seg[root].L = build(L, mid);

        seg[root].R = build(mid + , R);

    }

    return root;

}

int upDate(int version, int L, int R, int val) {

    int root = ++tot;

    seg[root] = seg[version];

    seg[root].sum = seg[version].sum + ;

    if (L < R) {

        int mid = (L + R) >> ;

        if (val <= mid) seg[root].L = upDate(seg[version].L, L, mid, val);

        else seg[root].R = upDate(seg[version].R, mid + , R, val);

    }

    return root;

}

int query(int u, int v, int L, int R, int k) {

    if (L >= R) return L;

    int num = seg[seg[v].L].sum - seg[seg[u].L].sum;

    int mid = (L + R) >> ;

    if (num >= k) {

        return query(seg[u].L, seg[v].L, L, mid, k);

    } else return query(seg[u].R, seg[v].R, mid + , R, k - num);

}

int a[maxn];

vector<int> vc;

int getID(int val) {

    return lower_bound(vc.begin(), vc.end(), val) - vc.begin() + ;

}

const int down = -1e9, up = 1e9;

void work() {

    tot = ;

    vc.clear();

    int n, m;

    cin >> n >> m;

    for (int i = ; i <= n; ++i) {

        scanf("%d", a + i);

        vc.push_back(a[i]);

    }

    sort(vc.begin(), vc.end());

    vc.erase(unique(vc.begin(), vc.end()), vc.end());

//     for (int i = 0; i < vc.size(); ++i) {

//         printf("%d ", vc[i]);

//     }

    T[] = build(up, down);

    for (int i = ; i <= n; ++i) {

//        int id = getID(a[i]);

        T[i] = upDate(T[i - ], down, up, a[i]);

    }

    for (int i = ; i <= m; ++i) {

        int L, R, val;

        scanf("%d%d%d", &L, &R, &val);

//        val = (R - L + 1) - val + 1;

        int res = query(T[L - ], T[R], down, up, val);

        printf("%d\n", res);

    }

}

int main() {

    #ifdef local

    freopen("data.txt", "r", stdin);

    #endif // local

//    int t;

//    scanf("%d", &t);

//    while (t--) work();

    work();

    return ;

}

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

const int maxn =  + ;

struct Node {

    int L, R;

    int sum;

} seg[maxn << ];

int T[maxn], now;

int build(int L, int R) {

    ++now;

    seg[now].sum = ;

    if (L < R) {

        int mid = (L + R) >> ;

        seg[now].L = build(L, mid);

        seg[now].R = build(mid + , R);

    }

    return now;

}

int upDate(int version, int L, int R, int val, int xo) {

    int root = ++now;

    seg[root] = seg[version];

    seg[root].sum = seg[version].sum + xo;

    if (L < R) {

        int mid = (L + R) >> ;

        if (val <= mid) {

            seg[root].L = upDate(seg[version].L, L, mid, val, xo);

        } else {

            seg[root].R = upDate(seg[version].R, mid + , R, val, xo);

        }

    }

    return root;

}

int query(int version1, int version2, int L, int R, int be, int en) {

    if (L > R) return ;

    if (L >= be && R <= en) {

        return seg[version2].sum - seg[version1].sum;

    }

    int ans = ;

    int mid = (L + R) >> ;

    if (mid >= be) ans += query(seg[version1].L, seg[version2].L, L, mid, be, en);

    if (mid +  <= en) ans += query(seg[version1].R, seg[version2].R, mid + , R, be, en);

    return ans;

}

int pre[ + ];

int up = -1e9;

int en = 1e9;

void work() {

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; ++i) {

        int x;

        scanf("%d", &x);

        if (pre[x]) {

            int res = upDate(T[i - ], up, en, pre[x], -);

            T[i] = upDate(res, up, en, i, );

        } else T[i] = upDate(T[i - ], up, en, i, );

        pre[x] = i;

    }

    int q;

    cin >> q;

    while (q--) {

        int l, r;

        scanf("%d%d", &l, &r);

        printf("%d\n", query(T[l - ], T[r], up, en, l, r));

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

#endif // local

    work();

    return ;

}