Ex

#include <bits/stdc++.h>

using namespace std;

const int M = 70000 + 10;
int all[M], n, len;
vector<unordered_set<int>> s;

void init() {
    scanf("%d", &n);
    len = sqrt(n + .01) + 1;
    s.resize(len);
    for (int i = 0, t; i < n; ++i) {
        scanf("%d", all + i);
    }
    for (int i = 0; i < n; ++i) {
        s[i / len].insert(all[i]);
    }
}

inline int __attribute__((always_inline)) query(int a, int b, int number) {
    if(a == b) {
        if(all[a] == number) {
            return 1;
        }
        return 0;
    }
    int cl = a / len, cr = b / len;
    if (cl == cr) {
        for (int i = a; i <= b; ++i) {
            if (all[i] == number) {
                return 1;
            }
        }
        return 0;
    }

    for (int i = cl + 1; i <= cr - 1; ++i) {
        if (s[i].find(number) != s[i].end()) {
            return 1;
        }
    }

    for (int i = a, end = (cl + 1) * len - 1; i <= end; ++i) {
        if (all[i] == number) {
            return 1;
        }
    }
    for (int i = cr * len; i <= b; ++i) {
        if (all[i] == number) {
            return 1;
        }
    }
    return 0;
}

void solve() {
    int queries, a, b, number;
    scanf("%d", &queries);
    for (int i = 0; i < queries; ++i) {
        scanf("%d%d%d", &a, &b, &number);
        printf("%d", query(a - 1, b - 1, number));
    }
}

int main() {
    init();
    solve();
}