Intersection Floor Sum

問題文

正整数 $N$ と長さ $N$ の非負整数列 $A$ が与えられる。

$xy$ 座標平面上に $N$ 個の領域 $S_1, S_2, \dots, S_N$ がある。領域 $S_i$ は、$\left|y-ix\right| \le A_i$ を満たす点全体の集合である。

$1 \le i \lt j \le N$ を満たす $i, j$ について、 $S_i$ と $S_j$ の共通部分に含まれる点の $x$ 座標の最大値を $f(i, j)$ とする。

$\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}{\left\lfloor f(i, j) \right\rfloor}$ を求めよ。

制約

• 入力はすべて整数である。
• $2 \le N \le 5 \times 10^4$
• $0 \le A_i \le N$ $(1 \le i \le N)$

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル

サンプル 1

入力

5
2 0 4 1 3

出力

24

例えば、 $f(1, 2) = 3, f(2, 4) = \dfrac12$ である。