#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>


#define P 40
#define MOD 1000000007

using namespace std;

int upperBound(set<int> &s, int lb) {
    auto it = s.upper_bound(lb);
    return *it-1;
}

int lowerBound(set<int> &s, int lb) {
    auto it = s.lower_bound(lb);
    it--;
    return *it+1;
}



struct interval {
    int l;
    int r;
    int value;
    int index;
    int edgeDist;
    bool visited = false;
    interval(int l, int r, int value, int index, int edgeDistance): l(l), r(r), value(value), index(index), edgeDist(edgeDistance) {};
};

vector<long> catalineNumbers() {
    vector<long> seq(1000000, 0);
    for (int i = 1; i < 1000000; i++) {
        seq[i] = (seq[i-1] + i) % MOD;
    }
    return seq;
}

vector<long> catalineSum(vector<long> &cats) {
    vector<long> catSum(1000000, 0);
    catSum[0] = cats[0];

    for (int i = 1; i < cats.size(); i++) {
        catSum[i] = catSum[i-1] + cats[i];
    }

    return catSum;
}

vector<long> alternateSums(vector<long> &cats) {
    vector<long> oddSum(1000000, 0);
    oddSum[0] = cats[0];
    oddSum[1] = cats[1];

    for (int i = 2; i < cats.size(); i++) {
        oddSum[i] = oddSum[i-2] + cats[i];
    }

    return oddSum;
}



long computeBetween(long &remaining, long left, long right, vector<long> &catalineSeq) {

    long y = right;
    long x = (left + 1); // silly

    if (y >= x) {
        x = right + 1;
        y = left;
    }

    long answer = ((y+1)*((x*(x+1))/2) + x*catalineSeq[y]) % MOD;

    remaining = ((remaining-answer) + MOD)%MOD;

    return answer;
}

long computeMax(long &remaining, long left, long right, vector<long> &catalineSum, vector<long> &altSeq, vector<long> &catalineSeq) {
    long answer = ((remaining - catalineSeq[left]) + MOD)%MOD;

    long start = right + max(left-1,0l);
    long end = start - 2*max(min(left-1, right),0l);

    answer = ((answer - altSeq[start]) + MOD) % MOD;

    answer = (answer + altSeq[end])%MOD;
    answer = ((answer-catalineSum[end])+MOD)%MOD;

    remaining = ((remaining-answer)+MOD)%MOD;

    return answer;
}

long computeLeft(long &remaining, long left, long leftExtra, long right, vector<long> &catalineSum, vector<long> &altSeq, vector<long> &catalineSeq) {

    long answer = ((remaining - catalineSeq[left]) + MOD)%MOD;
    answer = ((answer - catalineSum[right]) + MOD)%MOD;

    long start = leftExtra + max(left-1,0l);
    long end = start - 2*min(leftExtra, max(left-1,0l));

    answer = ((answer - altSeq[start]) + MOD) % MOD;

    answer = (answer + altSeq[end])%MOD;
    answer = ((answer-catalineSum[end])+MOD)%MOD;

    remaining = ((remaining-answer)+MOD)%MOD;

    return answer;


}

long computeRight(long &remaining, long left, long right, long rightExtra, vector<long> &catalineSum, vector<long> &altSeq, vector<long> &catalineSeq) {
    long answer = remaining;
    answer = ((answer - catalineSum[left]) + MOD)%MOD;
    answer = ((answer - catalineSeq[rightExtra]) + MOD)%MOD;


    long start = right + max(rightExtra-1,0l);
    long end = start - 2*min(max(rightExtra-1,0l), right);

    answer = ((answer - altSeq[start]) + MOD) % MOD;

    answer = (answer + altSeq[end])%MOD;
    answer = ((answer-catalineSum[end])+MOD)%MOD;

    remaining = ((remaining-answer)+MOD)%MOD;

    return answer;
}

long computeRemaining(long n) {

    long ans = (n*(n+1))/2;
    ans = ans % MOD;

    ans = (ans*(ans+1))/2;
    ans = ans % MOD;

    return ans;
}



vector<long> expander(vector<long> &x) {
    vector<long> ans;

    for (int i = 0; i < x.size(); i++) {
        for (int j = 0; j < x.size()-i; j++) {
            long maximum = -1;
            for (int l = j; l <= j + i; l++) {
                maximum = max(x[l], maximum);
            }

            ans.push_back(maximum);
        }
    }

    return ans;


}


bool indexSort(const interval *x1, const interval *x2) {
    return x1->index < x2->index;
}

bool edgeSort(const interval *x1, const interval *x2) {
    if (x1->value == x2->value) {
        if (x1->edgeDist == x2->edgeDist) {
            return x1->index < x2->index;
        }
        return x1->edgeDist < x2->edgeDist;
    } else {
        return x1->value > x2->value;
    }
}

void addInterval(interval *it, int n, long &sum, long &remaining, vector<long> &catalineSums, vector<long> &catalineNums, vector<long> &catalineAlt) {
    if (it->visited) {
        return;
    }

    int value = it->value;
    it->visited = true;

    long left = it->index - max(it->l,0);
    long right = min(it->r,n-1) - it->index;
    long leftExtra = (it->index - it->l) - left;
    long rightExtra = (it->r - it->index) - right;

    if (it->l <= 0 && it->r >= n-1) {
        sum = (sum + it->value*computeMax(remaining, left,  right, catalineSums, catalineAlt, catalineNums)) % MOD;
    } else if (it->l <= 0) {
        sum = (sum + it->value*computeLeft(remaining, left, leftExtra, right, catalineSums, catalineAlt, catalineNums)) % MOD;
    } else if (it->r >= n-1) {


        sum = (sum + it->value*computeRight(remaining, left, right, rightExtra, catalineSums, catalineAlt, catalineNums)) % MOD;
    } else {
        sum = (sum + it->value*computeBetween(remaining, left, right, catalineNums)) % MOD;
    }
}

struct node {
    long value;
    int index;
    int edgeDist;
    node(long value, int index, int edgeDist): value(value), index(index), edgeDist(edgeDist) {};
};


long slowSolution(vector<node> nums) {
    vector<long> numsFix;

    for (int i = 0; i < nums.size(); i++) {
        numsFix.push_back(nums[i].value);
    }

    vector<long> nums2 = expander(numsFix);
    vector<long> nums3 = expander(nums2);

    long sum = 0;
    long fivers = 0;
    long ones = 0;

    for (int i = 0; i < nums3.size(); i++) {
        sum += nums3[i];
        if (nums3[i] == 9) {
            fivers++;
        } else if (nums3[i] == 4) {
            ones++;
        }
    }

    cout << "found " << fivers << endl;
    cout << "found " << ones << endl;
    cout << "size " << nums3.size() << endl;

    return sum;

}

bool sorter(const node &x1, const node &x2) {
    if (x1.value == x2.value) {
        if (x1.edgeDist == x2.edgeDist) {
            return x1.index < x2.index;
        }
        return x1.edgeDist < x2.edgeDist;
    } else {
        return x2.value < x1.value;
    }
}

int main() {

    int n;
    scanf("%d", &n);

    vector<node> nums;

    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        nums.push_back(node(x, i, min(i, n-i-1)));
    }


    set<int> s;

  //  long anserSlow = slowSolution(nums);

    vector<interval*> intervalsEdgeDist;
    vector<interval*> intervalIndex;

    sort(nums.begin(), nums.end(), sorter);

    for (int i = 0; i < n; i++) {

        node x = nums[i];

        s.insert(x.index);
        s.insert(x.index-n);
        s.insert(x.index+n);

        int left = lowerBound(s, x.index);
        int right = upperBound(s, x.index);
        int value = x.value;

        int edgeDist = x.edgeDist;

        interval* it = new interval(left,right,value, x.index, edgeDist);
        intervalsEdgeDist.push_back(it);
        intervalIndex.push_back(it);

    }

    sort(intervalsEdgeDist.begin(), intervalsEdgeDist.end(), edgeSort);
    sort(intervalIndex.begin(), intervalIndex.end(), indexSort);

    vector<long> catalineNums = catalineNumbers();
    vector<long> catalineSums = catalineSum(catalineNums);
    vector<long> catalineAlt = alternateSums(catalineNums);

    long remaining = computeRemaining(n);

    long sum = 0;


    interval* start = intervalsEdgeDist[0];
    addInterval(start, n, sum, remaining, catalineSums, catalineNums, catalineAlt);
    int left = start->index;
    int right = start->index;


    for (int i = 1; i < n; i++) {
        interval* next = intervalsEdgeDist[i];

        if (next->visited) {
            continue;
        }

        addInterval(next, n, sum, remaining, catalineSums, catalineNums, catalineAlt);

        int nextIndex = next->index;

        if (nextIndex > right) {
            for (int j = right+1; j < nextIndex; j++) {
                addInterval(intervalIndex[j], n, sum, remaining, catalineSums, catalineNums, catalineAlt);
            }
            right = nextIndex;

        } else if (nextIndex < left) {
            for (int j = nextIndex+1; j < left; j++) {
                addInterval(intervalIndex[j], n, sum, remaining, catalineSums, catalineNums, catalineAlt);
            }

            left = nextIndex;
        }
    }

    cout << sum << endl;
   // cout << anserSlow << endl;


}