#152. 楼兰图腾

楼兰图腾

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在完成了分配任务之后,西部 314\red{314} 来到了楼兰古城的西部。

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

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

西部 314\red{314} 认为这幅壁画所包含的信息与这 N\red N 个点的相对位置有关,因此不妨设坐标分别为(1,y1)\red{(1,y_1)} , (2,y2)\red{(2,y_2)} , ......\red{......} , (n,yn)\red{(n,y_n)} , 其中 y1yn\red{y_1\sim y_n}1\red 1n\red n 的一个排列。

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

如果三个点 (i,yi)\red{(i,y_i)} , (j,yj)\red{(j,y_j)} , (k,yk)\red{(k,y_k)} 满足 1i<j<kn\red{1\le i<j<k\le n}yi>yj\red{y _i>y_j} , yj<yk\red{y_j<y_k} ,则称这三个点构成 V\red V 图腾;

如果三个点 (i,yi)\red{(i,y_i)} , (j,yj)\red{(j,y_j)} , (k,yk)\red{(k,y_k)} 满足 1i<j<kn\red{1\le i<j<k\le n}yi<yj\red{y_i<y_j} , yj>yk\red{y_j>y_k} ,则称这三个点构成 \red ∧ 图腾;

西部 314\red{314} 想知道,这 n\red n 个点中两个部落图腾的数目。

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

输入格式

第一行一个数 n\red n

第二行是 n\red n 个数,分别代表 y1\red{y_1}y2\red{y_2} , ......\red{......} , yn\red{y_n}

输出格式

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

样例

输入样例

5
1 5 3 2 4

输出样例

3 4

提示

对于所有数据,n200000\red{n\le 200000} ,且输出答案不会超过 int64\red{int64}

数据结构3

未参加
状态
已结束
规则
IOI
题目
19
开始于
2023-1-9 12:00
结束于
2023-1-17 20:00
持续时间
200 小时
主持人
参赛人数
12