Fuel - Nhien lieu (But Wait, There Are Some Changes Version)


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 500M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

A transportation company is a regular customer of a fuel trading company. The fuel company has announced the selling prices of fuel for the next \(n\) days as a sequence of values \(a_1, a_2, \dots, a_n\). Because the transportation company is a loyal customer, it is given a special preferential policy from the fuel company, as follows: The selling price on day \(i\) is never higher than the price on the previous days. That is, if the announced price on day \(i\) is \(a_i\), and it is greater than the price actually purchased on day \(i-1\), then the transportation company is still allowed to buy fuel on day \(i\) at the price it purchased on day \(i-1\).

To estimate operating costs, the transportation company has raised \(q\) queries of the form \(L, R, x\), meaning: If the company starts buying fuel from day \(L\) to day \(R\), how many days will it end up buying fuel at price \(x\)?

Help the transportation company answer these \(q\) queries!

Input

  • The first line contains an integer \(n \ (1 \le n \le 10^5)\);
  • The next line contains \(n\) integers \(a_1, a_2, \dots, a_n \ (1 \le a_i \le 10^5)\);
  • The third line contains an integer \(q \ (1 \le q \le 10^5)\);
  • Each of the next \(q\) lines contains three integers \(L, R, x \ (1 \le L \le R \le N;\ 1 \le x \le 10^5)\).

Output

\(q\) lines, each containing the answer to one query.

Scoring

  • Subtask 1 (70%): \(n, q \le 10^3\).
  • Subtask 2 (30%): No additional constraints.

Examples

Example 1

input

8
12 15 10 11 9 20 8 8
3
2 7 12
5 8 9
2 5 15

output

0
2
1

Explanation

Initial price sequence: \(a = [12, 15, 10, 11, 9, 20, 8, 8]\)

Queries:

  • \((2, 7, 12)\to\) The purchase prices are, in order, \(15, 10, 10, 9, 9, 8\) - no day has a purchase price of \(12\).
  • \((5, 8, 9)\to\) The purchase prices are, in order, \(11, 9, 9, 8, 8\) - 2 days have a purchase price of \(9\).
  • \((2, 5, 15)\to\) The purchase prices are, in order, \(15, 10, 10, 9\) - 1 day has a purchase price of \(15\).

Comments

There are no comments at the moment.