Die Oberfläche eines außerirdischen Planeten besteht größtenteils aus Wüste, weshalb es selten regnet. Alle Pflanzen auf diesem Planeten sind Kakteen. Weil Regen so selten ist, haben die Kakteen eine Möglichkeit entwickelt, gemeinsam Wasser zu speichern.

Eine Region des Planeten ist eine zweidimensionale Ebene mit nur den Richtungen oben-unten und links-rechts. Dort stehen $N$ Kakteen unmittelbar nebeneinander in einer Reihe. Jeder Kaktus ist $1$ Meter breit; ihre Höhen können verschieden sein. Zur Verschönerung der Umgebung bleiben nur die Kakteen $S$ bis $E$ stehen. Danach regnet es ausreichend, um sämtliche Bereiche über den Kakteen zu füllen, die Wasser halten können. Das Wasser sammelt sich wie unten abgebildet. Betrachte alle Kakteen außerhalb des durch die Pfeile markierten Bereichs als entfernt.

Schreibe ein Programm, das für die Kaktushöhen und einen Bereich verbleibender Kakteen die gespeicherte Wassermenge als Fläche berechnet. Es werden höchstens $Q$ Bereiche angegeben. Jeder Bereich wird stets auf den Anfangszustand angewendet, in dem alle Kakteen vorhanden sind.

Du musst folgende Funktionen implementieren.

• void init( int H[] ): Wird genau einmal zu Beginn aufgerufen. $H$ ist ein Array (Vektor) der Größe $N$ mit den Kaktushöhen von links nach rechts. $N$ ist die Anzahl der Kakteen.
• int query( int S, int E ): Gib die Fläche des gespeicherten Wassers nach ausreichend Regen zurück, wenn nur die Kakteen $S$ bis $E$ verbleiben ($1 \le S \le E \le N$). Die Funktion wird höchstens $Q$-mal aufgerufen. Alle Aufrufe sind unabhängig: Entfernte Kakteen in einem Aufruf beeinflussen keinen anderen.

Implementierungsdetails

Reiche genau eine Datei namens cactus.cpp ein. Sie muss folgende Funktionen implementieren.

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

Die Funktionen müssen wie oben beschrieben arbeiten. Du darfst weitere Funktionen für den internen Gebrauch definieren. Der eingereichte Code darf keine Ein- oder Ausgabe ausführen und nicht auf andere Dateien zugreifen.

Beispielgrader

Der bereitgestellte Grader liest Eingaben in folgendem Format.

• Zeile 1: $N$, $Q$.
• Nächste Zeile: $N$ positive ganze Zahlen, die Kaktushöhen von links nach rechts.
• Nächste $Q$ Zeilen: zwei positive ganze Zahlen $S,E$, die Regen bei allein verbleibenden Kakteen $S$ bis $E$ angeben ($1 \le S \le E \le N$).

Der bereitgestellte Grader gibt die von deiner Funktion query() zurückgegebenen Werte aus, jeweils einen pro Zeile.

Beschränkungen

• $1 \le N \le 500\,000$, $1 \le Q \le 500\,000$; die Höhe jedes Kaktus beträgt mindestens $1$ und höchstens $10^9$.

Teilaufgaben

Teilaufgaben 1 (13 Punkte)

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

Teilaufgaben 2 (12 Punkte)

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

Teilaufgaben 3 (22 Punkte)

• Jeder Kaktus ist höchstens $20$ hoch.

Teilaufgaben 4 (34 Punkte)

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

Teilaufgaben 5 (69 Punkte)

• Keine zusätzlichen Beschränkungen über die ursprünglichen hinaus.

Beispiele

Eingabe 1

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

Hinweis

Unten ist ein Beispiel für den Ablauf deines Codes mit der obigen Eingabe dargestellt.