Norma

Time Limit: 20 Sec Memory Limit: 64 MB

Description

img

Input

第1行，一个整数N；

第2~n+1行，每行一个整数表示序列a。

Output

输出答案对10^9取模后的结果。

Sample Input

4
　2
　4
　1
　4

Sample Output

109

HINT

N <= 500000
　1 <= a_i <= 10^8

Solution

img

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 1000005;
const int MOD = 1e9;
const int INF = 2147483640;

int get()
{
    int res = 1, Q = 1; char c;
    while( (c = getchar()) < 48 || c > 57)
        if(c == '-') Q = -1;
    if(Q) res = c - 48;
    while( (c = getchar()) >= 48 && c <= 57)
        res = res * 10 + c - 48;
    return res * Q;
}


int n;
int val[ONE];
int Ans;

void Modit(int &a)
{
    if(a < 0) a += MOD;
    if(a >= MOD) a -= MOD;
}

struct power
{
    int Min, MinI;
    int Max, MaxI;
    int MinMax, MinMaxI;

    friend power operator -(power a, power b)
    {
        power c;
        Modit(c.Min = a.Min - b.Min),
        Modit(c.MinI = a.MinI - b.MinI),
        Modit(c.Max = a.Max - b.Max),
        Modit(c.MaxI = a.MaxI - b.MaxI),
        Modit(c.MinMax = a.MinMax - b.MinMax),
        Modit(c.MinMaxI = a.MinMaxI - b.MinMaxI);
        return c;
    }
}A[ONE];


int Sum(int a, int b)
{
    return (s64)(a + b) * (b - a + 1) / 2 % MOD;
}

void Solve(int L, int R)
{
    if(L == R)
    {
        Modit(Ans += (s64)val[L] * val[R] % MOD * 1);
        return;
    }

    int mid = L + R >> 1;

    int minn = INF, maxx = -INF;
    A[mid] = (power){0, 0, 0, 0, 0, 0};

    for(int j = mid + 1; j <= R; j++)
    {
        minn = min(minn, val[j]), maxx = max(maxx, val[j]),
        Modit(A[j].Min = A[j - 1].Min + minn),
        Modit(A[j].MinI = A[j - 1].MinI + (s64)minn * j % MOD),
        Modit(A[j].Max = A[j - 1].Max + maxx),
        Modit(A[j].MaxI = A[j - 1].MaxI + (s64)maxx * j % MOD),
        Modit(A[j].MinMax = A[j - 1].MinMax + (s64)minn * maxx % MOD),
        Modit(A[j].MinMaxI = A[j - 1].MinMaxI + (s64)minn * maxx % MOD * j % MOD);
    }

    minn = INF, maxx = -INF;
    int a = mid, b = mid;
    power del;

    for(int i = mid; i >= L; i--)
    {
        minn = min(minn, val[i]), maxx = max(maxx, val[i]);
        while(minn <= val[a + 1] && a + 1 <= R) a++;
        while(maxx >= val[b + 1] && b + 1 <= R) b++;
        if(a <= b)
        {
            Modit(Ans += (s64)maxx * minn % MOD * Sum(mid + 1 - i + 1, a - i + 1) % MOD);
            del = A[b] - A[a];
            Modit(Ans += (s64)maxx * del.MinI % MOD - (s64)maxx * del.Min % MOD * (i - 1) % MOD);
            del = A[R] - A[b];
            Modit(Ans += (s64)del.MinMaxI - (s64)del.MinMax * (i - 1) % MOD);
        }
        else
        {
            Modit(Ans += (s64)maxx * minn % MOD * Sum(mid + 1 - i + 1, b - i + 1) % MOD);
            del = A[a] - A[b];
            Modit(Ans += (s64)minn * del.MaxI % MOD - (s64)minn * del.Max % MOD * (i - 1) % MOD);
            del = A[R] - A[a];
            Modit(Ans += (s64)del.MinMaxI - (s64)del.MinMax * (i - 1) % MOD);
        }
    }

    Solve(L, mid), Solve(mid + 1, R);

}

int main()
{
    n = get();
    for(int i = 1; i <= n; i++)
        val[i] = get();
    Solve(1, n);
    printf("%d", Ans);
}