Codeforces 314C. Sereja and Subsequences

Codeforces 314C. Sereja and Subsequences

樹狀數組+找規律

Codeforces JAVA8 比 JAVA6 慢了快一倍.......

C. Sereja and Subsequences time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Sereja has a sequence that consists of n positive integers, a1,?a2,?...,?an.

First Sereja took a piece of squared paper and wrote all distinct non-empty non-decreasing subsequences of sequence a. Then for each sequence written on the squared paper, Sereja wrote on a piece of lines paper all sequences that do not exceed it.

A sequence of positive integers x?=?x1,?x2,?...,?xr doesn't exceed a sequence of positive integers y?=?y1,?y2,?...,?yr, if the following inequation holds: x1?≤?y1,?x2?≤?y2,?...,?xr?≤?yr.

Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo1000000007 (109?+?7).

Input

The first line contains integer n (1?≤?n?≤?105). The second line contains n integers a1,?a2,?...,?an (1?≤?ai?≤?106).

Output

In the single line print the answer to the problem modulo 1000000007 (109?+?7).

Sample test(s) input

1
42

output

42

input

3
1 2 2

output

13

input

5
1 2 3 4 5

output

719

/**
 * Created by ckboss on 14-9-8.
 */
import java.util.*;

public class SerejaandSubsequences {

    static final long mod = 1000000007;
    static int n;
    static long[] a = new long[100100];
    static long[] tree = new long[1000100];
    static long[] dp = new long[100100];

    static int lowbit(int x){
        return x&(-x);
    }

    static void ADD(int pos,long value){
        for(int i=pos;i<=1000010;i+=lowbit(i)){
            tree[i]+=value;
            if(tree[i]>=mod) tree[i]-=mod;
        }
    }

    static long SUM(int pos){
        long ret=0;
        for(int i=pos;i>0;i-=lowbit(i)){

            ret+=tree[i];
            if(ret>=mod) ret-=mod;
        }
        return ret;
    }

    public static void main(String[] args){

        Scanner in = new Scanner(System.in);

        n=in.nextInt();
        for(int i=1;i<=n;i++){
            a[i]=in.nextInt();
            long sum=SUM((int)a[i]);
            long jian=SUM((int)a[i])-SUM((int)(a[i]-1));
            long temp=((sum*a[i])%mod+a[i]-jian+mod)%mod;
            dp[i]=(dp[i]+temp)%mod;
            ADD((int)a[i],temp);
        }

        long ans=0;
        for(int i=1;i<=n;i++){
            ans=(ans+dp[i])%mod;
        }
        System.out.println(ans);
    }
}