Module: árvore de segmentos


Problem

2 /4


árvore de segmentos

Theory Click to read/hide

Error

Problem

Corwin e Blaze se preparam para invadir Amber para derrubar Erik. Para fazer isso, eles precisam formar um exército. No mundo onde eles estão localizados, existem n assentamentos dispostos em linha devido ao terreno. Sabe-se que no primeiro assentamento existem a1 guerreiros, no segundo - a2, em i -th - ai, em n-th - an. 
Às vezes, Corwin e Blaze descobrem que o assentamento ai tem um número de guerreiros diferente do esperado. Corwin e Blaze perguntam m vezes qual é o número máximo de guerreiros que um assentamento pode fornecer com mais guerreiros. Ajude-os a identificá-lo.

Entrada
Na primeira linha, os números n e m (1 <= n, m <= 100000) são inseridos - o número de assentamentos e o número de pedidos .
A segunda linha contém n números a1, a2 >, ..., an (1 <= ai <= 1000) - número de guerreiros em assentamentos.< /div >
As linhas m a seguir contêm os números t, l e r ( 1 <= l <= r <= n), (0 <= t <= 1) - se t é igual a 0 então l e r - limites de consulta. Caso contrário, l é o número da cidade e r é uma nova informação.

Impressão
Na linha i, imprima a resposta para a consulta i se ti=0, caso contrário imprima "-1".

 
Exemplos
# Entrada Saída
1
5 3
1 2 3 4 5
0 1 5
1 3 6
0 1 5
5
-1
6
 

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!