405736: GYM102056 K Desperate … Fire Survive

Rikka is running with her every cell to the hall where the contest will be held.

Well, EC Final is growing bigger and bigger... Thus more and more computers have been connected into the weak 2000W main wires. Heat is accumulating in every row.

When Rikka enters the hall, she finds LCR there rearranging the wires with the volunteers. However, the girl might not be able to do anything helpful but observing.

"Listen. We have no time to calculate parameters for the new circuit. Are you good at data structures? Help us, please..."

The circuitry is a sequence of $$$n$$$ nodes, where there are $$$m$$$ possible levels of nodes in total, numbered from $$$1$$$ to $$$m$$$. Since a $$$k$$$-level node has a power limit twice of a $$$(k-1)$$$-level one, Rikka could merge two adjacent $$$k$$$-level nodes into a $$$(k+1)$$$-level one if $$$k < m$$$. She can also remove any node at any time from the circuitry while the order of rest nodes remains.

The volunteers have $$$q$$$ queries in total. Each query contains a segment $$$[l,r]$$$ and an integer level $$$k$$$. Rikka needs to count how many sub-segments of the assigned segment (i.e. a segment $$$[x, y]$$$ such that $$$l\le x\le y\le r$$$) can provide a $$$k$$$-level node, which means it is possible to turn circuitry sequence $$$[x,y]$$$ into a single $$$k$$$-level node by merging adjacent nodes at the same level and removing nodes, where these two types of operations can be performed multiple times in any order. Notice that the level must be exactly $$$k$$$ rather than higher or lower.

The first line contains three integers $$$n,m,q~(1 \leq n,m,q \leq 2 \times 10^5)$$$, the length of the circuitry sequence, the maximal level and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$A_1, A_2, \dots, A_n~(1 \leq A_i \leq m)$$$, the levels of nodes in order.

Each of the following $$$q$$$ lines contains three integers $$$l,r,k~(1 \leq l \leq r \leq n, 1 \leq k \leq m)$$$, describing a query.

Multiple integers in the same line are separated by spaces.

Output $$$q$$$ lines; each contains one integer, the answer to that query.

5 5 5
1 1 1 1 1
1 5 1
1 5 2
1 5 3
1 5 4
1 5 5

15
10
3
0
0

5 5 5
4 3 2 1 1
1 5 1
1 5 2
1 5 3
1 5 4
1 5 5

9
10
9
6
1