Module: Segment tree


Problem

2 /4


segment tree

Theory Click to read/hide

Error

Problem

Corwin and Blaze prepare to invade Amber to overthrow Erik. To do this, they need to raise an army. In the world where they are located, there are n settlements arranged in a line due to the terrain. It is known that in the first settlement there are a1 warriors, in the second - a2, in i -th - ai, in n-th - an. 
Sometimes Corwin and Blaze find out that the ai settlement has a different number of warriors than expected. Corwin and Blaze ask you m times what is the maximum number of warriors a settlement can supply the most warriors. Help them identify it.

Input
In the first line, the numbers n and m (1 <= n, m <= 100000) are input - the number of settlements and the number of requests .
The second line contains n numbers a1, a2 >, ..., an (1 <= ai <= 1000) - number of warriors in settlements.
The following m lines contain the numbers t, l and r (1 <= l <= r <= n), (0 <= t <= 1) - if t is equal to 0 then l and r - query boundaries. Otherwise l is the city number and r is new information.

Imprint
On the i-th line print the answer to the i-th query if ti=0, otherwise print " ;-1".

 
Examples
# Input Output
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!