TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5953
  • Problem
  • P5953【序列的欢乐赛】序列最值
    Limits : Time Limit : - MS   Memory Limit : 262144 KB
    Description

    nodgd在刷题时经常遇到序列求最值的问题,于是他自己出了一道:

    一个长度为$n$的整数序列有$\frac{n(n+1)}{2}$个连续子序列,算出每个连续子序列中所有数的最小值。但是这样将得到的$\frac{n(n+1)}{2}$个结果,太多了nodgd懒得看,所以你只要告诉nodgd所有结果的和,nodgd就认为你全都算对了。

    Input Format

    第一行一个整数$n$。第二行$n$个整数$a_1,a_2,\dots,a_n$。

    Output Format

    输出一个数,表示所有连续子序列内的最小值的和。

    Sample Input 1

    3
    1 2 3

    Sample Output 1

    10

    Sample Input 2

    5
    123456 234567 345678 456789 567890

    Sample Output 2

    4074050

    Hint

    样例说明1
    $n=3$时有6个连续子序列,分别是[1],[2],[3],[1,2],[2,3],[1,2,3]。
    这6个子序列的最小值分别为1,2,3,1,2,1,所以答案是$1+2+3+1+2+1=10$。

    数据规模与约定
    对于30%的数据,\(n\le200\)
    对于60%的数据,\(n\le2000\)
    对于100%的数据,\(n\le200000\),$1\le a_i\le10^6$。


    Source  感谢nodgd