1910: 还是lis

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:11 通过:6

题目描述

    一个序列的LIS,是指从中选出一个子序列(不一定要连续,但是相对位置不能变化),这个子序列的每个元素是递增的,所有满足条件的子序列,长度最长的就是这个序列的LIS

    求一个序列A有多少个连续子序列的LIS与原序列相同。

    即求所有的<i,j>对数,满足LIS(A[i,j])=LIS(A[1,n]);

    其中A[i,j]表示( Ai,Ai+1,Ai+2,…,Aj)

输入格式

第一行一个整数n,表示A的长度。

接下来一行n个元素,表示A序列中的每个元素。每个元素的值不超过longint

输出格式

输出<i,j>的对数,表示A[i,j]LISA序列的LIS相同。

输入样例 复制

样例输入1:
3
1 2 3

样例输入2:
2
2 1

输出样例 复制

样例输出1:
1

样例输出2:
3

数据范围与提示

对于20%的数据,n的范围[1,20];

对于50%的数据,n的范围[1,100];

对于70%的数据,n的范围[1,1000];

对于100%的数据,n的范围[1,100000];