#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1000000009;
const int INF = 200006;
int n;

ll tree[4*INF],lazy[4*INF];
vector<ll> a;
void build(int st,int l, int r){
  if(l == r){
    tree[st] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(2 * st,l,mid);
  build(2 * st + 1 , mid + 1,r);
  tree[st] = max(tree[2*st],tree[2*st + 1]);
}
void _update(int st,int l,int r,int ql,int qr,int v){
    if(lazy[st] != 0){

        tree[st] += lazy[st];
        if(l != r){
        lazy[2*st] += lazy[st];
        lazy[2 * st + 1] += lazy[st];
        }
        lazy[st] = 0;
    }
    if(qr < l || ql > r || l > r)
        return;
    if(ql <= l && qr >= r){
        tree[st] += v;
        if(l != r){
            lazy[2*st] += v;
            lazy[2*st + 1] += v;
        }
        return;
    }
    int mid = (l + r) >> 1;
    _update(2*st,l,mid,ql,qr,v);
    _update(2*st + 1,mid + 1,r,ql,qr,v);
    tree[st] = max(tree[2*st],tree[2*st+ 1]);



}
ll get(int st,int l,int r,int ql,int qr){
    if(lazy[st] != 0){

        tree[st] += lazy[st];
        if(l != r){
        lazy[2*st] += lazy[st];
        lazy[2 * st + 1] += lazy[st];
        }
        lazy[st] = 0;
    }
    if(ql == l && qr == r)
        return tree[st];
    int mid = (l + r) >> 1;
    if(ql > mid)
        return get(2 * st + 1,mid + 1,r,ql,qr);
    if(qr <= mid)
        return get(2*st,l,mid,ql,qr);

    ll v1 = get(2*st,l,mid,ql,mid);
    ll v2 = get(2 * st+1,mid + 1,r,mid + 1,qr);
    return max(v1,v2);
}

void update(int l,int r,int v){
_update(1,0,n - 1,l,r,v);
}
ll rmq(int l,int r){
return get(1,0,n - 1,l,r);
}
vector<ll> get(){
    vector<ll>b;
    for(int i = 0;i < a.size() ; i++){
        for(int j = 0; j < a.size() - i; j++){
            int k = i + j;
            b.push_back(rmq(j,k));
        }
    }
    return b;
}


int main() {
    cin >> n;
    a.resize(n);
    for(int i = 0;i < n ; i++)
        cin >> a[i];
    build(1,0,n-1);
    a = get();
    n = a.size();
    build(1,0,n-1);
    a = get();
    ll ans = 0;
    for(int i = 0;i < a.size() ; i++)
         ans += a[i],ans %= MOD;
    cout << ans;
    return 0;
}