Remove the element

You are given an integer array A of size N. You can perform an operation exactly N number of times. In the operation, you can remove one element from array A and the operation will cost 

$A_i$ units if $i^{th}$ is removed from the array. The operation will take 1 second.

Elements of array A will keep on increasing every second until it is removed. Let $i^{th}$ element is $A_i$ at $j^{th}$ second. Then the $i^{th}$ the element will increase by $(j+1)\ast A_i$ and the element will become $A_i+(j+1)\ast A_i$ at $(j+1{)}^{th}$ second.

Your task is to find the minimum cost to remove all the elements from array A. As the answer can be very large, print the answer module ${10}^9+7$.

Example:

Input:  n = 2, arr = [3, 3]
Output: 9

Approach

C++

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
long long dp[100001];
void fact(long long n)
{

    dp[1] = 1;
    for (long long i = 2; i <= 100000; i++)
        dp[i] = (i * dp[i - 1]) % MOD;
}

long long removeElement(long long n, long long arr[])
{
    sort(arr, arr + n);
    long long ans = 0;
    long long j = 0;
    long long k = 1;
    for (long long i = n - 1; i > 0; i--)
    {
        ans = (ans + ((arr[i]) * dp[k]) % MOD) % MOD;
        k++;
    }
    ans = (ans + arr[0] * dp[n]) % MOD;
    return ans % MOD;
}
int main()
{

    fact(100000);

    long long n = 2;

    long long arr[n] = {3, 3};

    cout << removeElement(n, arr) << "\n";

    return 0;
}