Większość powierzchni pewnej obcej planety stanowią pustynie, więc rzadko pada tam deszcz. Wszystkie rośliny na tej planecie to kaktusy. Z powodu niedoboru deszczu kaktusy wyewoluowały sposób współpracy przy magazynowaniu wody.

Pewien obszar planety jest płaszczyzną dwuwymiarową z kierunkami jedynie góra–dół i lewo–prawo. Stoi tam $N$ kaktusów, przylegających do siebie w jednym rzędzie. Każdy ma szerokość $1$ metra, a ich wysokości mogą się różnić. Dla upiększenia okolicy pozostawiono tylko kaktusy od $S$ do $E$. Następnie spadło dość deszczu, by wypełnić wodą każdy obszar nad kaktusami, który może ją zatrzymać. Woda zbiera się jak na rysunku poniżej. Kaktusy poza zakresem wskazanym strzałkami należy uważać za usunięte.

Napisz program, który dla wysokości kaktusów i zakresu pozostawionych kaktusów obliczy ilość zatrzymanej wody jako pole powierzchni. Podanych będzie najwyżej $Q$ zakresów. Każdy zakres stosuje się zawsze do stanu początkowego, w którym istnieją wszystkie kaktusy.

Zaimplementuj następujące funkcje.

• void init( int H[] ): Wywoływana dokładnie raz na początku. $H$ to tablica (wektor) rozmiaru $N$, zawierająca wysokości kaktusów od lewej do prawej. $N$ jest liczbą kaktusów.
• int query( int S, int E ): Zwróć pole zatrzymanej wody po dostatecznie obfitym deszczu, gdy pozostają tylko kaktusy od $S$ do $E$ ($1 \le S \le E \le N$). Funkcja zostanie wywołana najwyżej $Q$ razy. Wszystkie wywołania są niezależne: usunięcie kaktusów w jednym wywołaniu nie wpływa na inne.

Szczegóły implementacji

Prześlij dokładnie jeden plik o nazwie cactus.cpp. Musi on implementować następujące funkcje.

• void init( int H[] )
• long long query( int S, int E )

Funkcje mają działać zgodnie z powyższym opisem. Możesz definiować inne funkcje do użytku wewnętrznego. Przesłany kod nie może wykonywać operacji wejścia ani wyjścia ani uzyskiwać dostępu do innych plików.

Przykładowy program oceniający

Dostarczony program oceniający czyta dane w następującym formacie.

• Wiersz 1: $N$, $Q$.
• Następny wiersz: $N$ dodatnich liczb całkowitych, czyli wysokości kaktusów od lewej do prawej.
• Kolejne $Q$ wierszy: dwie dodatnie liczby całkowite $S,E$, oznaczające deszcz przy pozostawieniu tylko kaktusów od $S$ do $E$ ($1 \le S \le E \le N$).

Dostarczony program oceniający wypisuje wartości zwrócone przez twoją funkcję query(), po jednej w wierszu.

Ograniczenia

• $1 \le N \le 500\,000$, $1 \le Q \le 500\,000$; wysokość każdego kaktusa wynosi co najmniej $1$ i najwyżej $10^9$.

Podzadania

Podzadania 1 (13 punktów)

• $1 \le N \le 5\,000$, $1 \le Q \le 5\,000$

Podzadania 2 (12 punktów)

• $1 \le N \le 5\,000$

Podzadania 3 (22 punktów)

• Wysokość każdego kaktusa wynosi najwyżej $20$.

Podzadania 4 (34 punktów)

• $1 \le N \le 100\,000$, $1 \le Q \le 100\,000$

Podzadania 5 (69 punktów)

• Brak dodatkowych ograniczeń poza pierwotnymi.

Przykład

Wejście 1

10 3
1 3 2 5 1 4 6 2 1 3
2 8
2 4
7 9

Uwagi

Poniżej pokazano przykładowy przebieg twojego kodu dla powyższego wejścia.