P10741: 图腾计数

---

【题目描述】

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

【输入】

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

【输出】

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

【提示】

对于30%的数据，N<=100
对于100%的数据，N<=200000

题目类型~

高级算法及数据结构-树状数组 

咻咻~

提交答案 状态 返回