序列之争4

序列之争4

描述

输入一个长度为n的整数序列A1~An,满足其中的数两两各不相同且构成一个1~n的排列。现在进行如下定义:
若存在1<=i<j<k<=n且Ai>Aj,Aj<Ak,则称Ai,Aj,Ak组成了一个形状A
若存在1<=i<j<k<=n且Ai<Aj,Aj>Ak,则称Ai,Aj,Ak组成了一个形状B
求这个序列中形状A和形状B的个数
第一行一个数n
第二行有n个数A1~An
两个数,中间用空格隔开,依次为形状A的个数和形状B的个数
10%的数据 n<=600
40%的数据 n<=5000
100%的数据 n<=200000,答案不超过long long

输入样例

5
1 5 3 2 4

输出样例

3 4

样例解释

形状A的组成情况有如下3种
5 3 4
5 2 4
3 2 4
形状B的组成情况有如下4种
1 5 2
1 5 3
1 5 4
1 3 2

时空限制

每个测试点1s
空间16384KB

数据范围

10%的数据 n<=600
40%的数据 n<=5000
100%的数据 n<=200000,答案不超过long long

信息

难度
5
分类
(无)
标签
(无)
递交数
37
已通过
15
通过率
41%
被复制
3
上传者

相关

在下列训练计划中:

历届小兰赛综合训练

在下列比赛中:

2019-1-22寒假集训2