ACM-ICPC-OJ训练营

问题 E: 连号区间

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

题目描述

小明这些天一直在思考这样一个奇怪而有趣的问题：

在 1∼N 的某个排列中有多少个连号区间呢？

这里所说的连号区间的定义是：

如果区间 [L,R] 里的所有元素（即此排列的第 L个到第 R 个元素）递增排序后能得到一个长度为 R−L+1的“连续”数列，则称这个区间连号区间。

当 N很小的时候，小明可以很快地算出答案，但是当 N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

第一行是一个正整数 N，表示排列的规模。
第二行是 N 个不同的数字 Pi，表示这 N个数字的某一排列。

输出一个整数，表示不同连号区间的数目。

4
3 2 4 1

满足答案的数组是连续的。

1≤N≤10000,

1≤Pi≤N