#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include<math.h>
#include <algorithm>
using namespace std;

long long int sum(vector<long long int> A)
{
    vector<long long int> B;
    for(long long int k=0;k<A.size();k++)
    {
        for(long long int i=0;i<A.size()-k;i++)
        {
            int j=i+k;
            long long int max=A[i];
            for(int l=i;l<=j;l++)
                if(max<A[l])
                    max=A[l];
            B.push_back(max);
        }
    }
    vector<long long int> S;
    for(long long int k=0;k<B.size();k++)
    {
        for(long long int i=0;i<B.size()-k;i++)
        {
            int j=i+k;
            long long int max=B[i];
            for(int l=i;l<=j;l++)
                if(max<B[l])
                    max=B[l];
            S.push_back(max);
        }
    }
    long long int sum=0;
    for(int i=0;i<S.size();i++)
        sum+=S[i];
    return (fmod(sum,(pow(10,9))));
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int n;
    cin >> n;
    vector<long long int> A;
    for (int i=0;i<n;i++)
    {
        long long int temp;
        cin >> temp;
        A.push_back(temp);
    }
    long long int result=sum(A);
    cout << result;
    return 0;
}