某個外星球的表面大部分是沙漠，因此很少下雨。這個星球上所有的植物都是仙人掌。由於雨水極為稀少，仙人掌演化出了相互合作儲存水的方法。

星球上的某個區域是只有上下、左右方向的二維平面。這個區域中有 $N$ 株仙人掌緊挨著排成一行。每株仙人掌的寬度都是 $1$ 公尺，高度可以不同。為了美化環境，只保留第 $S$ 株到第 $E$ 株仙人掌，之後下了足夠多的雨，使仙人掌上方所有能蓄水的區域都積滿了水。積水情況如下圖所示。圖中箭頭所標範圍之外的仙人掌應視為已被移除。

請編寫程式，給定仙人掌的高度和保留下來的仙人掌範圍，以面積計算積水量。最多會給出 $Q$ 個範圍。每個範圍都始終作用於所有仙人掌均存在的初始狀態。

你需要實作以下函式。

• void init( int H[] )：只在最開始呼叫一次。$H$ 是一個大小為 $N$ 的陣列（向量），按從左到右的順序存放仙人掌的高度。$N$ 是仙人掌的數量。
• int query( int S, int E )：當只保留第 $S$ 株到第 $E$ 株仙人掌並下了足夠多的雨後，回傳積水的面積（$1 \le S \le E \le N$）。這個函式最多呼叫 $Q$ 次。所有呼叫相互獨立，即一次呼叫中移除仙人掌不會影響其他呼叫。

實作細節

你必須提交恰好一個名為 cactus.cpp 的檔案。該檔案中必須實作以下函式。

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

這些函式應按上文所述運作。你可以定義其他函式供內部使用。提交的程式碼不得進行輸入輸出，也不得存取其他檔案。

評測程式範例

提供的評測程式按以下格式讀取輸入。

• 第 1 行：$N$、$Q$。
• 下一行：$N$ 個正整數，按從左到右的順序表示仙人掌的高度。
• 接下來 $Q$ 行：兩個正整數 $S,E$，表示只保留第 $S$ 株到第 $E$ 株仙人掌時下雨（$1 \le S \le E \le N$）。

提供的評測程式將你的 query() 函式回傳的值逐行輸出，每行一個。

資料範圍

• $1 \le N \le 500\,000$，$1 \le Q \le 500\,000$；仙人掌的高度至少為 $1$，至多為 $10^9$。

子任務

子任務 1 (13 分)

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

子任務 2 (12 分)

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

子任務 3 (22 分)

• 仙人掌的高度至多為 $20$。

子任務 4 (34 分)

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

子任務 5 (69 分)

• 除原有資料範圍外，沒有額外限制。

範例

輸入格式 1

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

說明

對於上述輸入，你的程式碼的執行過程範例如下。