# Sereja and Subsequences

## 题目描述

Sereja has a sequence that consists of $n$ positive integers, $a_1, a_2, \ldots, a_n$.
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=x_1, x_2, \ldots, x_r$ doesn’t exceed a sequence of positive integers $y=y_1, y_2, \ldots, y_r$, if the following inequation holds: $x_1 \le y_1, x_2 \le y_2, \ldots, x_r \le y_r$.
Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo $1000000007$ ($10^9+7$).

## 算法分析

$$f_{a_i}=(1+f_1+f_2+ \cdots +f_{a_i})a_i$$

## 代码

<?php
const MAX_NUM = 1000000;
const MOD = 1000000007;

$tree = array(); for ($i = 0; $i <= MAX_NUM; ++$i) array_push($tree, 0); function add($pos, $val) { global$tree;
for (; $pos <= MAX_NUM;$pos += $pos & -$pos) {
$tree[$pos] += $val;$tree[$pos] -= (int) ($tree[$pos] / MOD) * MOD; } } function get($pos) {
global $tree;$ret = 0;
for (; $pos;$pos -= $pos & -$pos) {
$ret +=$tree[$pos];$ret -= (int) ($ret / MOD) * MOD; } return$ret;
}

$n = fgets(STDIN);$a = explode(' ', trim(fgets(STDIN)));
for ($i = 0;$i < $n; ++$i) {
$sum = get($a[$i]); add($a[$i],$sum * $a[$i] + $a[$i] - $sum + get($a[$i] - 1)); }$ans = get(MAX_NUM);
$ans -= (int) ($ans / MOD) * MOD;
echo \$ans . "\n";
?>


418 I'm a teapot