1544: 阿正的子母序列

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:15

题目描述

最近阿正刚学习完字符串,对解决子串和母串的问题乐此不疲,但希望阿正进步的学长又给阿正出了一道序列和子序列的难题,你能帮帮阿正吗? 


给定一个长度为N序列A,对A的子序列B有如下定义: 

(1)    BA中的K个元素组成;(1<=K<=N 

(2)    B中所有元素按在a中的出现顺序进行排列; 

1 2 4 5 3 的子序列可以是 1 2 4 和 1 2 3 ,但不能是2 1 4 或者 6 1 4 

而连续子序列则是B中的元素要在A中连续,即1 2 4 5 A的一个连续子序列,但1 2 4 3虽然是A的子序列,却不是连续子序列。 



定义A的两个子序列P、Q相等,当且仅当满足以下条件: 

(1)    两个子序列长度相等; (1<=KP=KQ<=N) 

(2)    两个子序列中所有对应元素都相等,即对于子序列中所有的元素,都有Pi=Qi(0<=i<k); 

(3)    两个子序列首元素在母序列中出现的位置相等; 

对于第三个条件,意即在母序列 "1 2 3 1 2 3" 中,首元素出现在0的第一个"1 2 3"与首元素出现在3的第二个"1 2 3" 不相等。



现在学长给阿正了一个长度为N的序列A,不仅要让阿正求出A中不相等的连续非递减子序列的数量,同时,学长将一个序列的权值定义为该序列的长度,要让阿正求出A的所有不相同的连续非递减子序列权值总和。 

输入

第一行一个正整数N,代表序列A的长度; (0<N<=10000) 

第二行N个整形范围内的整数,依次代表序列A中的各元素。 

输出

第一行一个正整数代表A的不同的连续非递减子序列个数。 

第二行一个正整数代表A的所有连续非递减子序列权值总和。 

样例输入 复制

5
1 2 4 5 3

样例输出 复制

11
21

提示

对于样例中的序列:1 2 4 5 3 的连续非递减子序列,有(每个[ ]为一个)
[1]、[1 2]、[1 2 4]、[1 2 4 5]
[2]、[2 4]、[2 4 5]
[4]、[4 5]
[5]
[3]
共11个;
对上述非递减子序列,权值依次为:
1、2、3、4
1、2、3
1、2
1
1
总和为21。

来源/分类