Prédios

Sufia é a prefeita de Uderlândia (uma grande cidade do estado de Ginas Merais) e ela percebeu que a temperatura da cidade aumentou muito no ultimo ano. Para descobrir a razão de tal fenômeno Sufia contrata uma equipe de pesquisadores. Após varias semanas de estudo, eles constatam que os prédios muito altos barram o vento que chega a cidade e para resolver o problema todos os prédios da cidade deve conter no máximo uma altura de $x$ $metros$.

Como a cidade possui muitos prédios altos Sufia resolve que só vai demolir os prédios com uma altura maior que $y$ $metros$, note que $y$ pode ser maior, menor ou igual a $x$, que estiverem entre algumas ruas cruciais. Sufia está muito ocupada com a prefeitura da cidade e pediu sua ajuda para saber quantos prédios serão demolidos. Ela irá lhe fornecer uma lista com todos os $N$ prédios de Uderlândia e outra com $Q$ perguntas onde cada pergunta é composta por duas ruas $l$ e $r$, para cada perguntas responda quantos prédios possuem altura maior que $y$ $metros$ entre as ruas $l$ e $r$. Vale lembrar que cada rua possui somente $1$ prédio e que $y$ pode variar de pergunta para pergunta.

Entrada

A primeira linha da entrada possui dois inteiros $N$ $(1 \leq N \leq 10^5)$ e $Q$ $(1 \leq Q \leq 10^5)$, representando, respectivamente, o números de prédios em Uderlândia e o número de perguntas de Sufia.

A segunda linha da entrada contém N inteiros $p_1,$ $p_2,$ $...,$ $p_{n-1},$ $p_n$, representando a altura (em metros) dos prédios na cidade, onde $p_i$ $(1 \leq p_i \leq 10^6)$ representa a altura do i-ésimo prédio.

As próximas $Q$ linha contém, cada uma, três inteiros $l$, $r$ $(1 \leq l < r \leq N)$ e $y$ $(1 \leq y \leq 10^6)$ representando uma pergunta de Sufia.

Saída

Imprima a resposta para cada uma das perguntas de Sufia.

Exemplos

5 3
1 7 2 1 3
1 5 12
2 4 1
3 5 2

0
2
1

10 7
23 2 13 3 5 8 11 4 31 16
3 5 9
2 7 4
1 4 20
6 10 12
1 10 10
7 9 7
5 8 1

1
4
1
2
5
2
4