#include <bits/stdc++.h>

using namespace std;
#define mod 1000000009

int max(vector<int>a,int l,int r)
{
    int m=a[l];
    for(int i=l+1;i<=r;i++)
    {
        if(m<a[i])
            m=a[i];
    }
    return m;
}

int solve(vector <int> a)
{
    int sum=0;
    //  Return the sum of S(S(A)) modulo 10^9+7.
    vector<int>b;
    for(int k=0;k<a.size();k++)
    {
        for(int i=0;i< a.size()-k;i++)
        {
            int m= max(a,i,i+k);
            b.push_back(m);
                
         }
    }
    vector<int>s;
    
    for(int k=0;k<b.size();k++)
    {
        for(int i=0;i< b.size()-k;i++)
        {
            int m= max(b,i,i+k);
            s.push_back(m);
                
         }
    }
    int i;
    for(i=0;i<s.size();i++)
        sum= (sum%mod+ s[i]%mod)%mod;
    return sum;
    
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int a_i = 0; a_i < n; a_i++){
       cin >> a[a_i];
    }
    int result = solve(a);
    cout << result << endl;
    return 0;
}