codeforces 1067F (Educational Codeforces Round 65 (Rated for Div. 2) F. Scalar Queries ) 樹狀數組計算貢獻

F. Scalar Queries

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array a1,a2,…,ana1,a2,…,an. All aiai are pairwise distinct.

Let's define function f(l,r)f(l,r) as follows:

• let's define array b1,b2,…,br−l+1b1,b2,…,br−l+1, where bi=al−1+ibi=al−1+i;
• sort array bb in increasing order;
• result of the function f(l,r)f(l,r) is ∑i=1r−l+1bi⋅i∑i=1r−l+1bi⋅i.

Calculate (∑1≤l≤r≤nf(l,r))mod(109+7)(∑1≤l≤r≤nf(l,r))mod(109+7), i.e. total sum of ff for all subsegments of aa modulo 109+7109+7.

Input

The first line contains one integer nn (1≤n≤5⋅1051≤n≤5⋅105) — the length of array aa.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109, ai≠ajai≠aj for i≠ji≠j) — array aa.

Output

Print one integer — the total sum of ff for all subsegments of aa modulo 109+7109+7

Examples

input

Copy

4
5 2 4 7
           

output

Copy

167
           

input

Copy

3
123456789 214365879 987654321
           

output

Copy

582491518
           

Note

Description of the first example:

• f(1,1)=5⋅1=5f(1,1)=5⋅1=5;
• f(1,2)=2⋅1+5⋅2=12f(1,2)=2⋅1+5⋅2=12;
• f(1,3)=2⋅1+4⋅2+5⋅3=25f(1,3)=2⋅1+4⋅2+5⋅3=25;
• f(1,4)=2⋅1+4⋅2+5⋅3+7⋅4=53f(1,4)=2⋅1+4⋅2+5⋅3+7⋅4=53;
• f(2,2)=2⋅1=2f(2,2)=2⋅1=2;
• f(2,3)=2⋅1+4⋅2=10f(2,3)=2⋅1+4⋅2=10;
• f(2,4)=2⋅1+4⋅2+7⋅3=31f(2,4)=2⋅1+4⋅2+7⋅3=31;
• f(3,3)=4⋅1=4f(3,3)=4⋅1=4;
• f(3,4)=4⋅1+7⋅2=18f(3,4)=4⋅1+7⋅2=18;
• f(4,4)=7⋅1=7f(4,4)=7⋅1=7

題意：

定義f(l,r)：從l位置到r位置取出來，然後排序，i*val求和

求所有區間的和（并且ai不相同！！！）

思路：

首先肯定要往計數貢獻這方面考慮，先亂想一下，每次對于i位置，那麼有貢獻的是他這個數目前包括了多少個區間以及前面比它小的數和後面比它小的數，因為這樣才會讓他的位置往後移動，舉個例子，比如

5

1 5 2 4 7

首先我們單看1~i - 1位置給i的貢獻，

1是沒有的，因為前面沒有比它小的

5前面有1，但是1做了幾次貢獻呢？可以發現其實是從1到5目前位置和後面的位置1都是做了貢獻的，是以就是(n - i + 1) * 1

2也是一樣，前面隻有1對它的貢獻就是

1 5 2

1 5 2 4

1 5 2 7

是以一樣(n - i + 1) * 1

4,前面有1和2比它小，

1 5 2 4

1 5 2 4 7

5 2 4 

5 2 4 7 

2 4

2 4 7 

4前面有1,5,2，1做了n - i + 1次，我們把5的貢獻看成2做的，2做了n - i + 1 * 3

這樣就可以得到一個計算貢獻的式子

i的貢獻 =  {1到i - 1,之間所有比它小的數}的下标 * (n - i + 1)

計算i後面比它小的數的貢獻也是一樣，另外還要把他自己算進去就是i * (n - 1 + 1)，樹狀數組算貢獻就可以了（注意離散化和取模）

代碼：

ll n,k;
ll a[maxn];
struct node{  
    ll c[maxn];
    void add(int x,int val){ 
        while(x <= n){ 
            c[x] += val;
            x += lowbit(x);  
        }
        return ;
    }
    ll query(int x){ 
        ll res = 0;
        while(x){ 
            res += c[x];
            x -= lowbit(x);
        } 
        return res;
    }
}BT1,Bt2; 
std::vector<int> v; 
int getid(int x){ 
    return lower_bound(all(v),x) - v.begin() + 1;
}  
ll b[maxn]; 
ll num[maxn];
int main()
{ 
    ios;  
    while(cin >> n){ 
        ll ans = 0;
        for(int i = 1;i <= n;i++) cin >> a[i],v.pb(a[i]),b[i] = a[i];    
        sort(all(v));
        for(int i = 1;i <= n;i++) a[i] = getid(a[i]);    
        for(int i = 1;i <= n;i++){  
            add2(num[i],    mul1(BT1.query(a[i]), (n - i + 1))   );
            BT1.add(a[i],i);    
            wt(num[i]);
            add2(num[i],(n - i + 1) * i % mod);   
        } 
        for(int i = n;i >= 1;i--){
            add2(num[i], mul1(Bt2.query(a[i]),i) );
            Bt2.add(a[i],n - i + 1);
            add2(ans,num[i] * b[i] % mod); 
        }
        wt(ans);
    }
    return 0;
}