题目描述

在完成了分配任务之后，西部 314 来到了楼兰古城的西部。

相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(V)，一个部落崇拜铁锹(∧)，他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。

西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 $n$ 个点，经测量发现这 $n$ 个点的水平位置和竖直位置是两两不同的。

西部 314 认为这幅壁画所包含的信息与这 $n$ 个点的相对位置有关，因此不妨设坐标分别为 $(1,y_1),(2,y_2),\dots,(n,y_n)$，其中 $y_1 \sim y_n$ 是 $1$ 到 $n$ 的一个排列。

西部 314 打算研究这幅壁画中包含着多少个图腾。

如果三个点 $(i,y_i),(j,y_j),(k,y_k)$ 满足 $1 \le i < j < k \le n$ 且 $y_i > y_j, y_j < y_k$，则称这三个点构成 V 图腾；

如果三个点 $(i,y_i),(j,y_j),(k,y_k)$ 满足 $1 \le i < j < k \le n$ 且 $y_i < y_j, y_j > y_k$，则称这三个点构成 ∧ 图腾；

西部 314 想知道，这 $n$ 个点中两个部落图腾的数目。

因此，你需要编写一个程序来求出 V 的个数和 ∧ 的个数。

输入格式

第一行一个数 $n$。

第二行是 $n$ 个数，分别代表 $y_1，y_2,\dots,y_n$。

输出格式

两个数，中间用空格隔开，依次为 V 的个数和 ∧ 的个数。

样例

输入样例：

5
1 5 3 2 4

输出样例：

3 4

样例解释

$n=5$，排列为 $[1,5,3,2,4]$。

点的坐标： 1: (1,1) 2: (2,5) 3: (3,3) 4: (4,2) 5: (5,4)

V 图腾：中间点比两边低，即 $y_i > y_j$ 且 $y_j < y_k$（$i<j<k$）。

枚举中间点 $j$：

• $j=2$（$y=5$）：左边小于它的有 $1$ 个（$y=1$），右边小于它的有 $2$ 个（$y=3,2$），不能构成 V（要求中间低）。
• $j=3$（$y=3$）：左边大于它的有 $1$ 个（$y=5$），右边大于它的有 $1$ 个（$y=4$），可以构成 $1$ 个 V。
• $j=4$（$y=2$）：左边大于它的有 $2$ 个（$y=5,3$），右边大于它的有 $1$ 个（$y=4$），可以构成 $2$ 个 V。

V 总数 = $0+1+2=3$。

∧ 图腾：中间点比两边高，即 $y_i < y_j$ 且 $y_j > y_k$（$i<j<k$）。

枚举中间点 $j$：

• $j=2$（$y=5$）：左边小于它的有 $1$ 个（$y=1$），右边小于它的有 $2$ 个（$y=3,2$），可以构成 $1×2=2$ 个 ∧。
• $j=3$（$y=3$）：左边小于它的有 $2$ 个（$y=1,? 注意 y=5>3 不算），所以是 $1$ 个（$y=1$），右边小于它的有 $1$ 个（$y=2$），可以构成 $1×1=1$ 个 ∧。
• $j=4$（$y=2$）：左边小于它的有 $1$ 个（$y=1$），右边小于它的有 $1$ 个（$y=?$ 右边 $y=4>2$，没有小于它的），所以为 $0$。
• $j=5$（$y=4$）：左边小于它的有 $3$ 个（$y=1,3,2$），右边没有，所以为 $0$。

∧ 总数 = $2+1+0+0=3$？不对，样例输出是 $4$。可能漏算 $j=1$ 或 $j=5$？中间点 $j$ 必须左右都有点，所以 $j=1$ 和 $j=5$ 不考虑。

重新计算： $j=2$：左边小于它的：1 → 1 个；右边小于它的：3,2 → 2 个，所以 ∧ 数 = $1×2=2$。 $j=3$：左边小于它的：1 → 1 个；右边小于它的：2 → 1 个，所以 ∧ 数 = $1×1=1$。 $j=4$：左边小于它的：1 → 1 个；右边小于它的：无，所以 $0$。 总计 $3$，与样例 $4$ 不符。

检查 V： $j=3$：左边大于它的：5 → 1 个；右边大于它的：4 → 1 个，V 数 = $1×1=1$。 $j=4$：左边大于它的：5,3 → 2 个；右边大于它的：4 → 1 个，V 数 = $2×1=2$。 总计 $3$，与样例一致。

那么 ∧ 应该为 $4$，可能 $j=5$ 也算？但 $j=5$ 右边没有点，不能作为中间点。

实际上 ∧ 的个数为：对于每个位置 $j$，左边比 $y_j$ 小的个数 × 右边比 $y_j$ 小的个数？不对，∧ 要求中间高，即 $y_i<y_j$ 且 $y_j>y_k$，所以是左边比 $y_j$ 小的个数 × 右边比 $y_j$ 小的个数。

计算： $j=1$：左边无，不考虑。 $j=2$：左边比 $5$ 小：1 → 1 个；右边比 $5$ 小：3,2,4 中的 3,2,4 都比 5 小？3<5, 2<5, 4<5，所以是 3 个？之前错误看成右边比它小的只有 3,2，漏了 4？但 4 在右边，且 4<5，所以右边有 3 个比它小。那么 ∧ 数 = $1×3=3$。 $j=3$：$y=3$，左边比它小：1 → 1 个；右边比它小：2 → 1 个，所以 $1×1=1$。 $j=4$：$y=2$，左边比它小：1 → 1 个；右边比它小：无（4>2），所以 $0$。 $j=5$：不考虑右边。

总计 $3+1=4$，与样例一致。

所以正确算法：
V 数 = 对于每个 $j$，左边比 $y_j$ 大的个数 × 右边比 $y_j$ 大的个数。
∧ 数 = 对于每个 $j$，左边比 $y_j$ 小的个数 × 右边比 $y_j$ 小的个数。

数据范围

• $n \le 200000$
• 输出答案不超过 int64
• $y_1 \sim y_n$ 是 $1$ 到 $n$ 的一个排列

时空限制

• 时间限制：1 秒
• 空间限制：64 MB