Przy głównej autostradzie w Bajlandii postawiono bramki pobierające opłaty za wjazd na dany odcinek autostrady. Bramki ponumerowane są kolejnymi liczbami naturalnymi od 0 do n. Bajlandia jak powszechnie wiadomo jest wyspą, więc autostrada otacza ją w koło, a bramka ostatnia o numerze n pobiera opłatę za przejazd na odcinku od bramki n do bramki 0.
Bajlandzka Dyrekcja Dróg Krajowych i Autostrad zastanawia się, czy na danym odcinku autostrady maksymalna opłata za przejazd jakiegokolwiek odcinka pomiędzy dwiema kolejnymi bramkami nie jest zbyt wysoka.
Napisz program, który znając ilość bramek i kwoty pobierane przez bramki wyznaczy dla każdego podanego przedziału maksymalną kwotę pobierana przez jakąkolwiek bramkę na tym odcinku.
Pierwszy wiersz wejścia zawiera dwie liczby całkowite n z zakresu
1..400000 oraz k z zakresu 1..200000, oznaczające
odpowiednio ilość bramek i ilość przedziałów.
W wierszu drugim zapisano n+1 liczb całkowitych z zakresu
0..109 - liczba numer i w wierszu jest opłatą
pobieraną przez bramkę o numerze i-1.
W każdym z kolejnych k wierszy wejścia zapisano parę liczb całkowitych
x i y (x<=y) z zakresu 0..n,
oznaczających numery dwóch bramek.
Dla każdej wczytanej pary liczby x i y należy wypisać maksymalną opłatę pobraną przez którąkolwiek z bramek o numerach od x do y (bramkę ostatnią również przejeżdzamy).
Dla danych podanych na wejściu:
10 5 26 5 20 0 33 10 45 12 27 30 34 1 3 2 9 0 6 6 10 2 2
Poprawną odpowiedzią jest wyjście:
20 45 45 45 20
Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5
Opcje zadania:
Biblioteki : iostream iomanip cmath Limit czasu : 0.5 s Limit pamięci : 32 MB Słowa niedozwolone :