1613 timus

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <sstream>
#include <ctime>

#define pb push_back
#define mp make_pair
#define PI 3.1415926535897932384626433832795
#define ALL(x) x.begin(), x.end()
#define F first
#define S second
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,-1,sizeof(x))
#define pw(x) (1ull<<(x))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
const int INF = 2147483647;
const ll LLINF = 9223372036854775807LL;

struct qu {
  int l,r,num;
};

const int maxn = 200000;
int a[maxn];
int so[maxn];
int ans[maxn];
int col[maxn];
int p[maxn];
int n,qc;
qu q[maxn];
int sc = 0;
int bl;

bool comp(int a, int b) {
  return (q[a].l/bl<q[b].l/bl) || (q[a].l/bl==q[b].l/bl && q[a].r<q[b].r);
}

int main() {
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  cin >> n;
  for (int i=0;i<n;i++) {
    scanf("%d", &a[i]);
    so[sc++] = a[i];
  }
  bl = (int)(sqrt(n));
  cin >> qc;
  for (int i=0;i<qc;i++) {
    scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].num);
    so[sc++] = q[i].num;
  }
  sort(so, so+sc);
  for (int i=0;i<n;i++) a[i] = (int)(lower_bound(so, so+sc, a[i])-so);
  for (int i=0;i<qc;i++) q[i].num = (int)(lower_bound(so, so+sc, q[i].num)-so);
  for (int i=0;i<qc;i++) p[i] = i;
  sort(p, p+qc, comp);
  int l = 0, r = -1;
  for (int i=0;i<qc;i++) {
    qu &cur = q[p[i]];
    cur.l--; cur.r--;
    while (r<cur.r) {
      r++;
      col[a[r]]++;
    }
    while (l<cur.l) {
      col[a[l]]--;
      l++;
    }
    while (l>cur.l) {
      l--;
      col[a[l]]++;
    }
    while (r>cur.r) {
      col[a[r]]--;
      r--;
    }
    if (col[cur.num]!=0) ans[p[i]] =1;
  }
  for (int i=0;i<qc;i++) printf("%d", ans[i]);
  return 0;
}