Với một dãy số ~p~ gồm ~k~ phần tử ~p_1,p_2,\ldots,p_k~, định nghĩa hàm số ~f(p)~ như sau:

• ~f(p)=0~ nếu ~k=1~;

• Nếu ~k>1~, ~f(p)~ là giá trị lớn nhất của

  ~\left\lceil\dfrac{|p_j-p_i|}{j-i}\right\rceil~

  với mọi ~1 \le i<j \le k~.</p>

Với số thực ~x~, ký hiệu ~\lceil x\rceil~ là số nguyên nhỏ nhất không nhỏ hơn ~x~. Ví dụ:

~\left\lceil\dfrac{7}{3}\right\rceil =\lceil2.3333\ldots\rceil=3~,

~\left\lceil\dfrac{7}{4}\right\rceil =\lceil1.75\rceil=2~ và ~\lceil4\rceil=4~.

Cho dãy số ~a~ gồm ~n~ phần tử ~a_1,a_2,\ldots,a_n~.

Yêu cầu: Hãy tính tổng giá trị của hàm ~f~ trên tất cả các đoạn con khác rỗng ~a[l..r]~ của dãy ~a~, tức là:

~S=\displaystyle\sum_{l=1}^{n}\sum_{r=l}^{n}f(a[l..r])~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ là độ dài của dãy ~a~ ~(n \le 2 \times 10^5)~;

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,\ldots,a_n~ ~(1 \le a_i \le 10^8)~.

Output

Một số nguyên duy nhất là tổng ~S~ tìm được.

Scoring

Sample Input 1

3
4 5 2

Sample Output 1

7

Sample Input 2

7
2 6 8 1 5 10 3

Sample Output 2

129

Notes

Ở ví dụ thứ nhất:

• ~f(a[1..1])=f(a[2..2])=f(a[3..3])=0~;

• ~f(a[1..2])=\left\lceil\dfrac{|5-4|}{2-1}\right\rceil=1~;

• ~f(a[1..3])=\left\lceil\dfrac{|2-5|}{3-2}\right\rceil=3~;

• ~f(a[2..3])=\left\lceil\dfrac{|2-5|}{3-2}\right\rceil=3~.

Vậy ~S=0+0+0+1+3+3=7~.