Tổng hàm số

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

• $f(p)=0$ nếu $k=1$;
• Ngược lại ($k>1$), $f(p)$ là giá trị lớn nhất của $\lceil {\displaystyle \frac{|p_j-p_i|}{j-i}}\rceil$ với mọi $1\le i<j\le k$.

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$ (tức $x$ được làm tròn lên). Ví dụ: $\lceil {\displaystyle \frac{7}{3}}\rceil =\lceil 2.3333\dots \rceil =3$, $\lceil {\displaystyle \frac{7}{4}}\rceil =\lceil 1.75\rceil =2$, $\lceil 4\rceil =4$.

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

Yêu cầu: Hãy tính tổng giá trị của hàm số trên với tất cả các đoạn con khác rỗng $a[l..r]$ của dãy $a$, nói cách khác, hãy tính:

$$S=\sum _{l=1}^n\sum _{r=l}^{n}f(a[l..r])$$

Dữ liệu vào

• Dòng thứ nhất chứa một số nguyên dương $n$ là độ dài dãy $a$.
• Dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

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

Ràng buộc

• $1\le n\le 2\times {10}^5$
• $1\le a_i\le {10}^8$ với mọi $1\le i\le n$

Subtasks

• Subtask 1 ($20\%$ số test): $n\le 80$.
• Subtask 2 ($20\%$ số test): $n\le 450$.
• Subtask 3 ($30\%$ số test): $n\le 5\times {10}^3$.
• Subtask 4 ($30\%$ số test): không có ràng buộc gì thêm.

Ví dụ