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