Problem 4833. -- TYVJ1432 楼兰图腾

4833: TYVJ1432 楼兰图腾

Time Limit: 5 Sec  Memory Limit: 256 MB
Submit: 89  Solved: 24
[Submit][Status][Web Board]

Description

平面上有 N(N≤〖10〗^5 ) 个点,每个点的横、纵坐标的范围都是 1~N,任意两个点的横、纵坐标都不相同。
若三个点 (x_1,y_1),(x_2,y_2),(x_3,y_3 ) 满足 x_1<x_2<x_3, y_1>y_2 并且 y_3>y_2,则称这三个点构成"v"字图腾。
若三个点 (x_1,y_1),(x_2,y_2),(x_3,y_3 ) 满足 x_1<x_2<x_3, y_1<y_2 并且 y_3<y_2,则称这三个点构成"^"字图腾。
求平面上"v"和"^"字图腾的个数。

Input

第一行一个数n 
第二行是n个数,分别代表y1,y2……yn

Output

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

Sample Input

5
1 5 3 2 4

Sample Output

3 4

HINT

Source

[Submit][Status]