La surface d’une planète extraterrestre est essentiellement désertique, si bien qu’il y pleut rarement. Toutes les plantes de cette planète sont des cactus. Comme la pluie est très rare, les cactus ont développé par évolution un moyen de coopérer pour stocker l’eau.

Une région de la planète est un plan bidimensionnel ne comportant que les directions haut-bas et gauche-droite. On y trouve $N$ cactus côte à côte en une rangée. Chaque cactus mesure $1$ mètre de large, et leurs hauteurs peuvent différer. Pour embellir les lieux, on ne garde que les cactus de $S$ à $E$. Il pleut ensuite suffisamment pour remplir toutes les zones au-dessus des cactus capables de retenir de l’eau. L’eau s’accumule comme illustré ci-dessous. Dans la figure, considérez que les cactus hors de l’intervalle indiqué par les flèches ont été retirés.

Écrivez un programme qui, étant donné les hauteurs et un intervalle de cactus conservés, calcule l’eau retenue sous forme d’aire. Au plus $Q$ intervalles sont donnés. Chaque intervalle s’applique toujours à l’état initial où tous les cactus sont présents.

Vous devez implémenter les fonctions suivantes.

• void init( int H[] ) : Appelée exactement une fois au début. $H$ est un tableau (vecteur) de taille $N$ contenant les hauteurs des cactus de gauche à droite. $N$ est le nombre de cactus.
• int query( int S, int E ) : Renvoyez l’aire de l’eau retenue après une pluie suffisante lorsque seuls les cactus de $S$ à $E$ restent ($1 \le S \le E \le N$). Cette fonction est appelée au plus $Q$ fois. Tous les appels sont indépendants : retirer des cactus lors d’un appel n’affecte pas les autres.

Détails d’implémentation

Soumettez exactement un fichier nommé cactus.cpp. Il doit implémenter les fonctions suivantes.

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

Ces fonctions doivent se comporter comme décrit ci-dessus. Vous pouvez définir d’autres fonctions à usage interne. Le code soumis ne doit effectuer aucune entrée ou sortie ni accéder à d’autres fichiers.

Correcteur d’exemple

Le correcteur fourni lit l’entrée au format suivant.

• Ligne 1 : $N$, $Q$.
• Ligne suivante : $N$ entiers strictement positifs, les hauteurs des cactus de gauche à droite.
• $Q$ lignes suivantes : deux entiers strictement positifs $S,E$, indiquant qu’il pleut lorsque seuls les cactus de $S$ à $E$ restent ($1 \le S \le E \le N$).

Le correcteur fourni affiche les valeurs renvoyées par votre fonction query(), une par ligne.

Contraintes

• $1 \le N \le 500\,000$, $1 \le Q \le 500\,000$ ; chaque cactus a une hauteur au moins égale à $1$ et au plus égale à $10^9$.

Sous-tâches

Sous-tâches 1 (13 points)

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

Sous-tâches 2 (12 points)

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

Sous-tâches 3 (22 points)

• Chaque cactus a une hauteur au plus égale à $20$.

Sous-tâches 4 (34 points)

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

Sous-tâches 5 (69 points)

• Aucune contrainte supplémentaire par rapport aux contraintes initiales.

Exemples

Entrée 1

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

Remarque

Un exemple d’exécution de votre code pour l’entrée ci-dessus est présenté ci-dessous.