O2 - Ochrana

Časový limit: 30s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Úloha

Vlády teraz zaviedli povinné nosenie rúška (resp. inej ochrany úst a nosa), čo znamenalo obrovský záujem o ne. Samozrejme dopyt zvyšuje cenu, takže sa objavilo množstvo priekupníkov. Vo veľkom nakupujú aj štátne organizácie, ktoré musia využívať verejné obstarávanie.

Pri nákupoch cez verejné obstarávanie sa vyberá zvyčajne najnižšia cena. Ako overiť, či vysúťažená cena bola naozaj najnižšia? Predstavme si, že vláda objednala pre svojich občanov respirátory. Z dostupných zverejnených cien v rôznych dňoch overte, či nákup bol efektívny. Teda zistite najmenšiu cenu dostupnú v období zverejnenia verejného obstarávania (čo je niekoľko dní). Napríklad si vezmime vývoj ceny respirátora FPP2. Aká bola minimálna cena v období 11/2019-12/2019 a aká v období medzi 22.3.2020 a 25.3.2020 ?

V rámci hackatonu vznikla myšlienka vytvoriť program, ktorý dokáže zistiť najnižšiu cenu v danom období. Nie všetky obchody sú na porovnávačoch, a takisto sú tam občas chybné údaje, takže je potrebné aby vytvorený program vedel tieto údaje aj upravovať. Vašou úlohou je vytvoriť program, ktorý načíta zhromaždené ceny za isté obdobie a postupne bude spracovávať požiadavky na zmenu (1 x y ... zmeň cenu v dni x na hodnotu y) a výpočet (2 x y ... vypíš najnižšiu cenu v období dní x až y). Dni sú číslované od jedna (dátumy spracovávať nemusíte).

Vstup

V prvom riadku vstupu je uvedené jediné celé číslo N, počet dní za ktoré máme údaje.
Druhý riadok obsahuje ceny C – celé čísla c₁, c₂, …, c_N oddelené medzerami (0 ≤ c_i ≤ 10⁹).
Nasleduje niekoľko riadkov s príkazmi, každý z nich je jedného z nasledujúcich tvarov (viď zadanie):

1 x y (1 ≤ x ≤ N, 0 ≤ y ≤ 10⁹)
2 x y (1 ≤ x ≤ y ≤ N)

Vstup je ukončený riadkom obsahujúcim jediné číslo 0.

Výstup

Váš program musí spracovať príkazy v poradí, v akom sú uvedené na vstupe. Pre každý príkaz na vypísanie minimálnej ceny v danom období musí na výstup vypísať jeden riadok a v ňom jedno celé číslo – minimum z príslušných cien v danom období.

Obmedzenia

O1

1 ≤ N ≤ 1 000
Príkazov na vstupe bude najviac 1 000.

O2

1 ≤ N ≤ 500 000
Príkazov na vstupe bude najviac 500 000.

Príklad

Vstup

7
5 7 2 8 9 1 7
2 1 7
2 1 3
1 3 6
2 1 3
0

Výstup

1
2
5

18 Domáce 2