Xorin was recently elected president in his country and he wants to make travelling from one place to another great again.
His country is rather peculiar, it is composed of N towns placed on a straight line, with a bidirectional road connecting any 2 adjacent ones.
The problem is that not all towns benefit from having a gas station, so travelers must plan in advance for the trip. Each traveler has a car with a given fuel capacity of C litres and any drive to an adjacent town consumes 1 litre of fuel.
When they get to a town which has a gas station, they can fill up the tank to the maximum capacity. Xorin noticed that some people were forced to take the bus because their tank was not large enough for some distances. So he decided that he was going to serve any request coming from the people for gas station construction in additional towns, as long as the proposal consists of a minimal number of gas stations being built.
Xorin's advisor took note of this situation and decided to help the people by telling them what is the minimal number of gas stations that need to be built, starting with the initial configuration, so as to make their trip possible. He now receives a lot of requests of the form A B C, meaning that the traveler wants to get from town A to town B with a tank of capacity C.
The tank is full when the travelers start their journey.
Input
On the first line there is the number of towns N.
On the second line there is an array of N binary digits, without any spaces, where digit i is 1 if town i has a gas station and 0 otherwise.
On the third line there will be an integer Q, representing the number of requests as described above.
The next Q lines contain the requests, in the form of 3 integers A, B, C each, separated by spaces.
Output
Q lines, on line i being the answer to request i, representing the minimal number of gas stations that need to be built in order to make the trip of traveler i possible.
Restrictions
- 1 ≤ N, Q ≤ 105
- 1 ≤ C ≤ N
- 1 ≤ A ≤ B ≤ N
- Xorin doesn't actually build gas stations for a traveler
Sample
| Input | Output | Explanation |
|---|---|---|
| 7 0110001 3 1 5 1 1 7 5 1 4 2 | 1 0 0 | The first traveler wants to go from town 1 to town 5. He has a capacity of 1 litre. In order to arrive at the 5th town, he will travel from 1 to 2, refuel at 2, travel from 2 to 3, refuel at 3, travel from 3 to 4 where he will be stuck as he has an empty reservoir and there is no gas station in 4. If we build a gas station in 4, than our traveler can saftely drive to it's destination, the 5th town. The second traveler could use the following stategy: Travel from 1 to 3, refuel and drive all the way from 3 to 7 (by consuming 4 litres). |
It can be observed that the queries can be divided in two categories. Those smaller than sqrt(n)(square root of n) and those bigger.
For the queries bigger than sqrt(n) the solution is simple. Go through the segments of 0's with length > sqrt(n) and calculate how many gas stations have to be built. The formula is length / capacity for full segments between A and B and almost identical for the suffix after A and prefix before B. The complexity for a query is O(sqrt(n)) because you can't have more segments of this type.
For queries smaller than sqrt(n) the formula is the same, but we have too many segments, so we have to do preprocessing to answer fast.
We can build an array L where L[i] = the length of i'th segment of 0's and Sum where Sum[i][j] = sum(L[x] / j) with x <= i and j <= sqrt(n). The preprocessing takes O(n*sqrt(n)). After these computations, we can see that for a query we need the range of full segments of 0's between A and B, this is also a simple precomputation. The query can be now answered in O(1) .
!Also the memory can be optimised from O(n*sqrt(n)) to O(n) by sorting the queries increasingly by capacity. But this wasn't a requirement for full score.
