CF474F Ant colony

Mole is hungry again. He found one ant colony, consisting of $ n $ ants, ordered in a row. Each ant $ i $ ( $ 1

The first line contains one integer $n$ ($1 ≤ n ≤ 10^5$), the size of the ant colony. The second line contains $n$ integers $s_1, s_2, \ldots, s_n$ ($1 ≤ s_i ≤ 10^9$), the strengths of the ants. The third line contains one integer $t$ ($1 ≤ t ≤ 10^5$), the number of test cases. Each of the next $t$ lines contains two integers $l_i$ and $r_i$ ($1 ≤ l_i ≤ r_i ≤ n$), describing one query.

Print to the standard output $t$ lines. The $i$-th line contains number of ants that Mole eats from the segment $[l_i, r_i]$.

In the first test battle points for each ant are $v = [4, 0, 2, 0, 2]$, so ant number $1$ is freed. Mole eats the ants $2, 3, 4, 5$. In the second test case battle points are $v = [0, 2, 0, 2]$, so no ant is freed and all of them are eaten by Mole. In the third test case battle points are $v = [2, 0, 2]$, so ants number $3$ and $5$ are freed. Mole eats only the ant $4$. In the fourth test case battle points are $v = [0, 1]$, so ant number $5$ is freed. Mole eats the ant $4$.