#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main() {
    int n; 
    scanf("%i", &n);
    int A[n];
    for (int a_i = 0; a_i < n; a_i++) {
       scanf("%i",&A[a_i]);
    }
    
    long int b=0;
    for(long int i=1;i<=n;i++){
        b=b+i;
    }
    int B[b];
    int g=-1;
    int max;
    for (int k=0;k<n;k++){
        for(int i=0;i<n-k;i++){
            max=A[i];
            g=g+1;
            for(int j=i;j<=i+k;j++){
                if(A[j]>max){
                    max=A[j];
                }
            }
            B[g]=max;
        }
    }
    
    
    long int sum;
    long int b1=0;
    for(long int i=1;i<=b;i++){
        b1=b1+i;
    }
    int B1[b1];
    int g1=-1;
    for (int k=0;k<b;k++){
        for(int i=0;i<b-k;i++){
            max=B[i];
            g1=g1+1;
            for(int j=i;j<=i+k;j++){
                if(B[j]>max){
                    max=B[j];
                }
            }
            B1[g1]=max;
            sum=sum+B1[g1];
        }
    }
    
    
    
    printf("%ld",sum%1000000000);
    return 0;
}