Problem
Der Bauchige lehrt Gregor Melekhov, einen Kormoranschlag mit einem Stein auszuführen. Als Ziele verwenden sie n Bäume, die in einer Reihe stehen und von 1 bis n nummeriert sind. Er hat die Festigkeit aller Bäume mit natürlichen Zahlen bewertet und sie aufgezeichnet. Für jeden Baum, den Melechow schneiden konnte, erhält er eine Punktzahl, die der auf dem Baum aufgenommenen Zahl entspricht, und wenn er nicht konnte, verliert er genauso viel.
Der Bauchredner bittet Gregory, die Bäume in aufsteigender Reihenfolge von l bis r zu schlagen. Melechow hat sich kürzlich an der Schulter verletzt, weil er den Baum nach und nach erfolgreich fällen kann, dh wenn er einen Baum mit der Nummer i gefällt, kann er den Baum mit der Nummer i + 1 nicht fällen, aber er kann den Baum mit der Nummer i + 2 usw. fällen.
Der bauchige
m bat Gregor einmal, Schläge auszuführen, aber er vergaß, welche melechischen Bäume er fällen konnte. Helfen Sie ihm festzustellen, wie viele Punkte Gregory für jeden Versuch erzielt hat.
Eingabe
Die erste Zeile enthält 2 Zahlen n und m (\(1 <= n, m <= 100000\))
Die zweite Zeile enthält n Zahlen - die Stärke aller Bäume, wobei an der Position i die Stärke des i -Baums geschrieben ist.
Die folgenden m Zeilen enthalten die Zahlenpaare l und r (\(1 <= l <= r <= n\)), die angeben, welcher Teil der Bäume, die Sie um das Abschneiden des Tannenbaums gebeten haben, gefällt wurde.
Ausgabe
Geben Sie für jede Anfrage aus, wie viele Punkte Gregory bei diesem Versuch verdient hat.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
6 6
1 2 3 4 5 6
1 6
1 5
2 6
2 5
2 4
2 2
|
-3
3
4
-2
3
2
|