Module: Árbol de segmentos


Problem

2 /4


Árbol de segmentos

Theory Click to read/hide

Error

Problem

Corwin y Blaze se preparan para invadir Amber para derrocar a Erik. Para hacer esto, necesitan formar un ejército. En el mundo donde se encuentran, hay asentamientos n dispuestos en línea debido al terreno. Se sabe que en el primer asentamiento hay guerreros a1, en el segundo - a2, en i-th - ai, en n-th - an. 
A veces, Corwin y Blaze descubren que el asentamiento ai tiene un número de guerreros diferente al esperado. Corwin y Blaze te preguntan m veces cuál es el número máximo de guerreros que un asentamiento puede proporcionar a la mayor cantidad de guerreros. Ayúdalos a identificarlo.

Entrada
En la primera línea, se ingresan los números n y m (1 <= n, m <= 100000) - el número de liquidaciones y el número de solicitudes .
La segunda línea contiene n números a1, a2 >, ..., an (1 <= ai <= 1000) - número de guerreros en asentamientos.< /div >
Las siguientes m líneas contienen los números t, l y r ( 1 <= l <= r <= n), (0 <= t <= 1) - si t es igual a 0 entonces l y r - límites de consulta. De lo contrario, l es el número de la ciudad y r es información nueva.

Impresión
En la línea i-th, imprima la respuesta a la consulta i-th si ti=0, de lo contrario imprime "-1".

 
Ejemplos
 

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!

# Entrada Salida
1
5 3
1 2 3 4 5
0 1 5
1 3 6
0 1 5
5
-1
6