For a sequence of integers [a1,a2,…an], define the function f(i) as follows: Take the first i elements of a (a1,a2,…ai) and sort them in non-decreasing order. Call this new sequence si. Let f(i) = 1 * s1 + 2 * s2 + …i * si.

Given a sequence of n integers, sort them in non-decreasing order then compute f(1) + f(2) + …+ f(n). As result may be very large, return it modulo(1e9+7).

Constraints : 1 <= n <= 10^6, 1<=a[i] <= 10^6.

Example :

Input:

n=3, a = [9, 5, 8]

Output: 80

Explanation :

s1 = [9]; f(1) = 1 * 9=9.

s2 = [5, 9]; f(2) = 1 * 5 + 2 * 9 = 23.

s3 = [5,8,9]; f(3) = 1 * 5 + 2 * 8 + 3 * 9 = 48.

f(1)+f(2)+…+f(n) = f(1)+f(2)+f(3) = 9+23+48=80.

My Logic :

long long solve(vector a)
{
long long count=0, n=a.size(), sum=0;
for(long long i=0; i<n; i++)
{
sort(a.begin(), a.begin()+count+1);
count++;
for(long long j=0; j<count; j++)
sum+=a[j]*(j+1);
}
return sum;
}

As always said, you should provide a link to the problem statement and it’s also highly recommended that you discuss your intended approach or the point you are stuck with

I can only wonder why you are trying so hard to hide this post with copy paste of irrelevant details on stack and asking moderators to “change content”.

I’m genuinely curious. What about this post is so incriminating that you need to try so hard to hide it?

Then who gave you this problem?? Also your current code cannot be optimized…Currently I can just say that you should try to find a relation between f(i) and f(i+1) in O(1) or O(log(n))

I am a beginner. I don’t know the source, but i assure you that i hiding because you asked me to give source then only i can share my problem. Nothing more than that.

Anyways it cannot be solved in O(n) Or perhaps I’m not smart enough.

Just compute \sum a_i \times (i+1) \times (n-i).

It’s easy to see that this is the answer because each term will always have i elements less than it so it’s weight will be i+1, and will be present in n-i prefixes.

First of all, thanks for reply. According to the logic suggest by everule1, i am getting wrong answer. You asked me where i am checking my answer is in my rough copy and getting wrong answer. I want to clarify that i am not doing any type of cheating and all but just asking my doubt. If you really want to help me then suggest me logic. If you are not interested in it then please don’t comment and if you think i am cheating then just flag my post.