code

long long specialSum(vector<int> arr, int n) {
    long long ans = 0, num, cnt;
    // write code here
    long long dp1[n+1], dp2[n+1];
    for (int i = 0; i <= n; i++) dp1[i] = dp2[i] = 0;
    vector <pair <long long, long long> > nums; // number, cnt
    nums.push_back({0, 0});
    long long curVal = 0;
    for (int i = 0; i < n; i++) {
        long long curNum = arr[i], curCnt = 1;
        while(nums.back().first >= curNum) {
            tie(num, cnt) = nums.back();
            nums.pop_back();
            curCnt += cnt;
            curVal -= cnt * num;
        }
        curVal += curCnt * curNum;
        nums.push_back({curNum, curCnt});
        dp1[i] = curVal;
    }
    nums.clear();
    nums.push_back({0, 0});
    curVal = 0;
    for (int i = n-1; i >= 0; i--) {
        long long curNum = arr[i], curCnt = 1;
        while(nums.back().first >= curNum) {
            tie(num, cnt) = nums.back();
            nums.pop_back();
            curCnt += cnt;
            curVal -= cnt * num;
        }
        curVal += curCnt * curNum;
        nums.push_back({curNum, curCnt});
        dp2[i] = curVal;
    }
    for (int i = 0; i < n; i++)
        ans = max(ans, dp1[i] + dp2[i] - arr[i]);

    return ans;
}