A maior parte da superfície de um planeta extraterrestre é deserto, pelo que raramente chove. Todas as plantas nesse planeta são catos. Como a chuva é tão escassa, os catos evoluíram uma forma de cooperar para armazenar água.

Uma região do planeta é um plano bidimensional com apenas as direções cima-baixo e esquerda-direita. Nela existem $N$ catos encostados uns aos outros numa fila. Cada cato tem $1$ metro de largura, e as suas alturas podem diferir. Para embelezar o ambiente, deixam-se apenas os catos de $S$ a $E$. Depois chove o suficiente para encher todas as áreas acima dos catos que podem reter água. A água acumula-se como mostrado abaixo. Na figura, considere removidos os catos fora do intervalo indicado pelas setas.

Escreva um programa que, dadas as alturas e um intervalo de catos restantes, calcule a água retida como uma área. São dados no máximo $Q$ intervalos. Cada intervalo é sempre aplicado ao estado inicial em que existem todos os catos.

Deve implementar as seguintes funções.

• void init( int H[] ): É chamada exatamente uma vez no início. $H$ é um array (vetor) de tamanho $N$ com as alturas dos catos da esquerda para a direita. $N$ é o número de catos.
• int query( int S, int E ): Devolve a área de água retida após chuva suficiente quando só ficam os catos de $S$ a $E$ ($1 \le S \le E \le N$). É chamada no máximo $Q$ vezes. Todas as chamadas são independentes: remover catos numa chamada não afeta as outras.

Detalhes de implementação

Deve submeter exatamente um ficheiro chamado cactus.cpp. Este ficheiro deve implementar as seguintes funções.

• void init( int H[] )
• long long query( int S, int E )

As funções devem comportar-se como descrito acima. Pode definir outras funções para uso interno. O código submetido não deve realizar entrada ou saída nem aceder a outros ficheiros.

Avaliador de exemplo

O avaliador fornecido lê a entrada no seguinte formato.

• Linha 1: $N$, $Q$.
• Linha seguinte: $N$ inteiros positivos, as alturas dos catos da esquerda para a direita.
• Próximas $Q$ linhas: dois inteiros positivos $S,E$, indicando que chove restando apenas os catos de $S$ a $E$ ($1 \le S \le E \le N$).

O avaliador fornecido imprime os valores devolvidos pela sua função query(), um por linha.

Restrições

• $1 \le N \le 500\,000$, $1 \le Q \le 500\,000$; a altura de cada cato é pelo menos $1$ e no máximo $10^9$.

Subtarefas

Subtarefas 1 (13 pontos)

• $1 \le N \le 5\,000$, $1 \le Q \le 5\,000$

Subtarefas 2 (12 pontos)

• $1 \le N \le 5\,000$

Subtarefas 3 (22 pontos)

• A altura de cada cato é no máximo $20$.

Subtarefas 4 (34 pontos)

• $1 \le N \le 100\,000$, $1 \le Q \le 100\,000$

Subtarefas 5 (69 pontos)

• Sem restrições adicionais às originais.

Exemplos

Entrada 1

10 3
1 3 2 5 1 4 6 2 1 3
2 8
2 4
7 9

Nota

Abaixo apresenta-se uma execução de exemplo do seu código para a entrada acima.