For fans of statistics (Editorial)

Let the array $v$ contain statistical data about the number of people transported by trams. For each number of transported people $x$, store a vector of indices where this value occurs. In other words, in the map representation $p[x]$, we keep the indices of the cities where exactly $x$ people were transported during the year.

A query of the form (l, r, x) is processed as follows:

• If the value $x$ is not present in the map structure, we immediately print '$0$'.

• Otherwise, using a binary search (lower_bound), find in the array $p[x]$ the first index not less than $l$.

• If the found index does not exceed $r$, then the value $x$ does indeed occur among the cities with indices from $l$ to $r$.

Example

Let us consider how the structure $p$ looks for the first example.

• p[123] = \{1\};

• p[314] = \{3\};

• p[434] = \{5\};

• p[666] = \{2, 4\};

For instance, to process the query (1, 5, 314), we need to perform the following steps:

• Check whether the array $p[314]$ exists;

• Then, using binary search in the array $p[314]$, find the smallest value not less than l = 1. In this case, the value is $1$;

• Since it does not exceed r = 5, the answer to the query is $1$.

Algorithm implementation

Let us define the data structures used:

• The array $v$ stores statistical data on the number of people transported by trams;

• The map $p$ contains, for each value $x$ occurring in the input array $v$, the list of indices (positions) where this value appears.

vector<int> v;
map<int, vector<int>> p;

Read the input data.

cin >> n;
v.resize(n + 1);
for (i = 1; i <= n; i++)
{
  cin >> v[i];

In city number $i$, $v[i]$ people were transported. The cities are numbered starting from $1$.

  p[v[i]].push_back(i);
}

Read the number of queries $q$.

cin >> q;

The answer will be generated in the string $result$.

result = "";

Process the $q$ queries (l, r, x) sequentially.

for (i = 0; i < q; i++)
{
  cin >> l >> r >> x;

If no city has transported $x$ passengers, record '$0$' as the answer.

  if (p.find(x) == p.end())
  {
    result += '0';
    continue;
  }

It is necessary to determine whether the array $p[x]$ contains at least one number in the range from $l$ to $r$. Search for the first occurrence in $p[x]$ that is not less than $l$.

  vector<int>::iterator it = lower_bound(p[x].begin(), p[x].end(), l);

If such a number exists and it is not greater than $r$, record '$1$' as the answer.

  if (it != p[x].end() && *it <= r)
    result += '1';
  else
    result += '0';
}

Print thre answer.

cout << result << endl;