Laiko ribojimas: 0.5s

Atminties ribojimas: 256MB

Duomenų failas: uzklausos.in

Rezultatų failas: uzklausos.out

Jei norite pateikti savo sprendimą - prisijunkite.

Užklausos

Jums duota n skaičių seka a_1,a_2,...,a_n ir q užklausų. Užklausa sudaryta iš trijų skaičių (i, j, k), (1\\leqi\\leqj\\leqn). Kiekvienai užklausai (i, j, k) turite rasti, kiek skaičių posekyje a_i,a_{i+1},...,a_j yra didesni už k.

Pradiniai duomenys

Pirmoje eilutėje yra skaičius n (1\\leqn\\leq30000) - skaičių sekos dydis.

Sekančioje eilutėje pateikta n skaičių seka a_1,a_2,...,a_n (1\\leqa_i\\leq10^9).

Trečioje eilutėje pateiktas vienas skaičius q (1\\leqq\\leq200000) - užklausų skaičius.

Sekančiose q eilučių pateikta po vieną užklausą (i, j, k) (1\\leqi\\leqj\\leqn,1\\leqk\\leq10^9).

Rezultatai

Kiekvienai užklausai atskirose eilutėse išveskite po vieną skaičių - keli elementai duotos sekos intervale [i,j] yra didesni už k.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2 
2
0
3