Problem
Chubaty ensina Grigory Melekhov a executar um golpe Baklan com um sabre. Como alvos, eles usam árvores n em uma linha, numeradas de 1 a n. Chubaty, estimou a força de todas as árvores por números naturais e os escreveu. Para cada árvore que Melekhov conseguiu cortar, ele recebe um número de pontos igual ao número escrito na árvore e, se não conseguiu, perde a mesma quantia.
Chubaty pede a Grigory para acertar as árvores de l a r, em ordem crescente de seus números. Melekhov recentemente machucou o ombro, então ele pode cortar uma árvore com sucesso todas as vezes, ou seja, se ele cortar uma árvore com o número i, ele não será capaz de cortar uma árvore com o número < code>i + 1, mas poderá cortar a árvore com o número i + 2 etc.
Chubat
m certa vez pediu a Grigory para desferir golpes, mas ele esqueceu quais árvores Melekhov poderia cortar. Ajude-o a determinar quantos pontos Gregory marcou em cada tentativa.
Entrada
A primeira linha contém 2 números n e m (\(1 <= n, m <= 100000 \))
A segunda linha contém n números - a força de todas as árvores, onde a força da árvore i é escrita na posição i.
As seguintes linhas m contêm pares de números l e r (\(1 < ; = l <= r <= n\)), significando qual pedaço de árvore Chubaty pediu para cortar.
Saída
Para cada consulta, imprima quantos pontos Grigory ganhou nesta tentativa.
Exemplos
| # |
Entrada |
Saída |
| 1 |
6 6
1 2 3 4 5 6
16
1 5
2 6
2 5
2 4
2 2
|
-3
3
4
-2
3
2
|