问题 25213 --图腾计数

25213: 图腾计数

时间限制: 1 Sec  内存限制: 128 MB
提交: 126  解决: 63
[提交][状态][讨论版][命题人:]

题目描述

      whitecloth 最近参观了楼兰图腾。图腾的所在地有一排N 个柱子,N个柱子的高度恰好为一个1 到N 的排列,而楼兰图腾就隐藏在这些柱子中。由于whitecloth 弱爆了,他只知道图腾由3 个柱子组成,这三个柱子组成了下凸或上凸的图形(>.<),所谓下凸,设三个柱子的高度从左到右依次为h1,h2,h3,那么h1>h2,h3>h2,上凸则满足h1<h2,h3<h2。现在whitecloth 也找不到图腾具体是哪三个柱子,他只想知道满足这两个形状的柱子有几组。

输入

第一行一个数N
接下来一行N 个数,依次表示每个柱子的高度

输出

一行两个数,表示下凸形状的数量和上凸形状的数量,用空格隔开

样例输入

5
1 5 3 2 4

样例输出

3 4

提示

对于30%的数据,N<=100

对于100%的数据,N<=200000

来源

 

[提交][状态]