You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

很显然，szm 妹妹又找到了你，这次她给了你一个长度为 $n$ 的数列 $a$。定义一个区间 $[l,r]$ 的价值为 $\left| \dfrac{\sum \limits_{i = l}^{r} a_i}{r - l + 1} - \dfrac{\max \limits_{i = l}^{r} a_i + \min \limits_{i = l}^{r} a_i}{2} \right|$。她想把这一段区间分给 Ryan 哥哥，但是她不想让区间的价值很高，所以她你需要求出你最多可以给 Ryan 哥哥几种区间，使得每个区间的价值都是所有区间中价值最低的。

输入格式

首先输入一行一个正整数 $n$。接下来一行输入一行 $n$ 个正整数，中间用空格隔开，表示数组 $a$。

输出格式

一行一个正整数，表示你的答案。

数据范围

对于 $30\%$ 的数据，保证 $n\leq 100$。

对于 $60\%$ 的数据，保证 $n\leq 1000$。

对于 $100\%$ 的数据，保证 $n\leq 5000$，$a_i\leq 10^9$。

样例 #1

样例输入 #1

6
1 1 4 5 1 4

样例输出 #1

12

样例 #2

样例输入 #2

16
1 4 1 4 2 1 3 5 6 2 3 7 3 0 9 5

样例输出 #2

43

样例 #3

样例输入 #3

见下发文件中 ex_math03.in。

样例输出 #3

见下发文件中 ex_math03.out。

样例 #4

样例输入 #4

见下发文件中 ex_math04.in。

样例输出 #4

见下发文件中 ex_math04.out。