Contribution Technique.....not memoization....fully explained
IntuitionThe key insight to solving this problem is that for any element in the array, we need to calculate how many times it appears as both a minimum and maxi
# Intuition
The key insight to solving this problem is that for any element in the array, we need to calculate how many times it appears as both a minimum and maximum element across all possible subsequences of size up to k. By sorting the array first, we can guarantee that for any position i, all elements to the left are smaller and all elements to the right are larger.

# Approach


First, we sort the array to establish a clear ordering of elements. This ensures that for any element at index i:

All elements to its left (indices 0 to i-1) are smaller
All elements to its right (indices i+1 to n-1) are larger


For each element arr[i], we calculate:

How many times it appears as a maximum element (considering elements to its left)
How many times it appears as a minimum element (considering elements to its right)


For calculating combinations efficiently, we use precomputed factorials and their modular inverses. This is crucial for handling large numbers and maintaining good time complexity.
For each element arr[i]:

We calculate 'more' = number of elements to its right (n-i)
We calculate 'less' = number of elements to its left plus itself (i+1)
For being the maximum element: we consider combinations with j (0 to min(k,less)-1) elements from the left
For being the minimum element: we consider combinations with j (0 to min(k,more)-1) elements from the right

# Complexity
- Time complexity:
O(n log n) for sorting
O(n * k) for processing each element and its combinations

- Space complexity:
O(MAX)

Where MAX is the size used for precomputing factorials

# Code
```cpp []
#define MOD 1000000007
#define ll long long

/*----------------------------Number Theory Stuff Below------------------------------------------------------------------------------------*/
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll modExpo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
ll mminvprime(ll a, ll b) {return modExpo(a, b - 2, b);}
ll combination(ll n, ll r, ll m, ll *fact, ll *ifact) {ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m;}
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
ll inverseModulo(ll n){return modExpo(n,MOD-2,MOD);}
/*----------------------------------------------------------------------------------------------------------------------------------------------------*/

const int MAX = 1e6; // Define the maximum value of n

vector<ll> fact(MAX + 1), inv_fact(MAX + 1);


// Binary exponentiation
ll bin_pow(ll base, ll exp, ll mod) {
    ll result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

void factorials() {
    fact[0] = 1;
    for (ll i = 1; i <= MAX; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    inv_fact[MAX] = bin_pow(fact[MAX], MOD - 2, MOD); // Using Fermat's Little Theorem for modular inversion
    for (ll i = MAX - 1; i >= 0; i--) {
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    }
}


// nCr calculation using precomputed factorials
ll nCr(int n, int k) {
    if (k > n) return 0;
    return (fact[n] * ((inv_fact[k] * inv_fact[n - k]) % MOD)) % MOD;
}

bool check=false;

class Solution {
public:
    int minMaxSums(vector<int>&arr, int k) {
        if(!check){
            factorials();
            check=true;
        }

        int ans=0;
        int n=arr.size();
        if(n==1){
            return arr[0]*2;
        }

        sort(arr.begin(),arr.end());

        for(int i=0;i<n;i++){
            int more=n-i;
            int less=i+1;
            cout<<more<<" "<<less<<" ";

            int sum1=0;
            for(int j=0;j<min(k,more);j++){
                int count=nCr(more-1,j);
                int sum=mod_mul(arr[i],count,MOD);
                sum1=mod_add(sum1,sum,MOD);
            }

            for(int j=0;j<min(k,less);j++){
                int count=nCr(less-1,j);
                int sum=mod_mul(count,arr[i],MOD);
                sum1=mod_add(sum1,sum,MOD);
            }
            ans=mod_add(ans,sum1,MOD);
            //ans=mod_add(ans,mod_mul(arr[i],2,MOD),MOD);
            cout<<ans<<endl;
        }
        return ans;
    }
};
```
['C++']