Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: intMax.in

Rezultatų failas: intMax.out

Jei norite pateikti savo sprendimą - prisijunkite.

Intervalo maksimumas

Jums duotas sveikųjų skaičių sąrašas a_1,a_2,a_3,...a_N, ir sąrašas užklausų. Kiekviena užklausa yra vieno iš dviejų tipų:

  1. Pakeisti skaičiaus a_i reikšmę į b.
  2. Pasakyti didžiausią reikšmę tarp skaičių a_p,a_{p+1},a_{p+2},...a_{q-1},a_q.

Pradiniai duomenys

Pirmojoje eilutėje pateikti skaičiai N,Q(1\\leqN\\leq100000, 1\\leqQ\\leq200000) - sąrašo ilgis, ir užklausų skaičius.

Antroje eilutėje yra N skaičių - pradinis sąrašas. 1\\leqa_i\\leq10^{9}.

Tolesnėse Q eilučių yra užklausos, po vieną kiekvienoje eilutėje.

Kiekviena užklausa susideda iš trijų skaičių t,p,q:
Jei t=1, tai reikia pakeisti elemento a_p reikšmę į q (1\\leqp\\leqN,1\\leqq\\leq10^{9}).
Jei t=2, tai reikia rasti didžiausią elementą iš a_p,...a_q(1\\leqp\\leqq\\leqN).

Rezultatai

Kiekvienai antro tipo užklausai išveskitę po skaičių - didžiausią reikšmę nurodytame intervale.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 6
1 2 3 2 1
2 4 5
1 5 5
2 2 4
2 1 5
1 3 1
2 1 4
 
2
3
5
2