小 Z 喜欢区间。

 小 Z 定义一个区间是美丽的，当且仅当这个区间的最大值或最小值不出现在区间 的开头和结尾。如 [3, 2, 4, 1] 不是一个美丽的区间，因为最小值 1 出现在了结尾；而 [2, 4, 1, 3] 是一个美丽的区间，因为 1, 4 没有出现在开头或结尾。 

小 Z 有一个排. 列. ，现在需要求出这个序列中有多少个子区间是美丽的。

输入第一行一个整数 n，表示排列的长度。

 第二行 n 个整数，p1, p2, . . . , pn，表示小 Z 的排列。

【样例 1 解释】
只有子区间 [2, 3, 1, 4, 6, 5] 和 [3, 1, 4, 6, 5] 是美丽的。

对于 20% 的数据，1 ≤ n ≤ 200； 

对于 40% 的数据，1 ≤ n ≤ 2000；

 另有 20% 的数据，排列 pi 随机生成； 

对于 100% 的数据，1 ≤ n ≤ 2 × 10^5
. 

区间dp，单调栈