给定一个由 n 个元素组成的数组 a。该数组的某些子段的不平衡值是该段中的最大元素和最小元素之间的差。数组的不平衡值是该数组的所有子段的不平衡值之和。
例如,数组 [1, 4, 1] 的不平衡值为 9,因为该数组有 6 个不同的子段:
- [1](从索引1到索引1),不平衡值为0;
- [1, 4](从索引1到索引2),不平衡值为3;
- [1, 4, 1](从索引1到索引3),不平衡值为3;
- [4](从索引2到索引2),不平衡值为0;
- [4, 1](从索引2到索引3),不平衡值为3;
- [1](从索引3到索引3),不平衡值为0;
你必须确定数组 a 的不平衡值。
输入
第一行包含一个整数 n (1 ≤ n ≤ 106) — 数组 a 的大小。
第二行包含 n 个整数 a1, a2... an (1 ≤ ai ≤ 106) — 数组的元素。
输出
打印一个整数 — a 的不平衡值。
示例
输入 #1
3 1 4 1
输出 #1
9