#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MOD = 1e9;
const int N = 500005;

int n;
int a[N];
int minL[N], maxL[N], minR[N], maxR[N];

// Các mảng cộng dồn phục vụ tính toán O(1)
int sum_j[N], sum_minR_j[N], sum_maxR_j[N], sum_prodR_j[N];
int sum_1[N], sum_minR[N], sum_maxR[N], sum_prodR[N];

int divide_and_conquer(int l, int r) {
    if (l == r) {
        // Đoạn con độ dài 1: min * max * length = a[l] * a[l] * 1
        return (a[l] % MOD * a[l] % MOD) % MOD;
    }

    int m = (l + r) >> 1;
    int ans = (divide_and_conquer(l, m) + divide_and_conquer(m + 1, r)) % MOD;

    // Tiền xử lý cực trị cho nửa bên trái [l, m]
    minL[m] = maxL[m] = a[m];
    for (int i = m - 1; i >= l; i--) {
        minL[i] = min(minL[i + 1], a[i]);
        maxL[i] = max(maxL[i + 1], a[i]);
    }

    // Tiền xử lý cực trị cho nửa bên phải [m + 1, r]
    minR[m + 1] = maxR[m + 1] = a[m + 1];
    for (int j = m + 2; j <= r; j++) {
        minR[j] = min(minR[j - 1], a[j]);
        maxR[j] = max(maxR[j - 1], a[j]);
    }

    // Tạo các mảng prefix sum tổng cho nửa bên phải để tính nhanh
    // Lưu ý: Mọi phép tính nhân/cộng cần được lấy modulo cẩn thận
    auto get_mod = [](int x) { return (x % MOD + MOD) % MOD; };

    for (int j = m + 1; j <= r; j++) {
        int r_min = minR[j] % MOD;
        int r_max = maxR[j] % MOD;
        int r_prod = (r_min * r_max) % MOD;

        sum_1[j] = get_mod(sum_1[j - 1] + 1);
        sum_j[j] = get_mod(sum_j[j - 1] + j);
        
        sum_minR[j] = get_mod(sum_minR[j - 1] + r_min);
        sum_minR_j[j] = get_mod(sum_minR_j[j - 1] + r_min * j);
        
        sum_maxR[j] = get_mod(sum_maxR[j - 1] + r_max);
        sum_maxR_j[j] = get_mod(sum_maxR_j[j - 1] + r_max * j);
        
        sum_prodR[j] = get_mod(sum_prodR[j - 1] + r_prod);
        sum_prodR_j[j] = get_mod(sum_prodR_j[j - 1] + r_prod * j);
    }

    // Dùng 2 con trỏ p1 và p2 để tìm ranh giới nơi minR và maxR bị chế ngự bởi minL và maxL
    int p1 = m + 1; // p1 là vị trí đầu tiên mà minR[p1] < minL[i]
    int p2 = m + 1; // p2 là vị trí đầu tiên mà maxR[p2] > maxL[i]

    for (int i = m; i >= l; i--) {
        while (p1 <= r && minR[p1] >= minL[i]) p1++;
        while (p2 <= r && maxR[p2] <= maxL[i]) p2++;

        // Chia các đoạn j thành các khoảng dựa trên p1 và p2 để tính toán đóng góp từng phần
        // Ta có thể đẩy tất cả các điều kiện so sánh vào các hàm tính khoảng tổng [L, R] thu được từ p1, p2
        // Để code ngắn gọn và tránh nhầm lẫn chỉ số, ta biểu diễn qua một hàm lambda tính tổng đoạn [L, R]
        auto query_sum = [&](int L, int R) {
            if (L > R) return 0LL;
            int total = 0;
            
            // Lấy mẫu vị trí bất kỳ (chọn L) để biết mối quan hệ min/max của khoảng này với nhánh trái i
            int j_sample = L;
            int final_min = (minR[j_sample] < minL[i]) ? minR[j_sample] : minL[i];
            int final_max = (maxR[j_sample] > maxL[i]) ? maxR[j_sample] : maxL[i];
            
            // Tách các trường hợp phụ thuộc vào việc min, max lấy từ bên nào
            bool min_from_left = (minR[j_sample] >= minL[i]);
            bool max_from_left = (maxR[j_sample] <= maxL[i]);

            int cur_minL = minL[i] % MOD;
            int cur_maxL = maxL[i] % MOD;

            if (min_from_left && max_from_left) {
                // Trọng số = minL * maxL * (j - i + 1)
                int factor = (cur_minL * cur_maxL) % MOD;
                int sum_len = get_mod((sum_j[R] - sum_j[L - 1]) - (i - 1) * (sum_1[R] - sum_1[L - 1]));
                total = (factor * sum_len) % MOD;
            } 
            else if (!min_from_left && !max_from_left) {
                // Trọng số = minR * maxR * (j - i + 1)
                int term1 = get_mod((sum_prodR_j[R] - sum_prodR_j[L - 1]));
                int term2 = get_mod((sum_prodR[R] - sum_prodR[L - 1]) * (i - 1));
                total = get_mod(term1 - term2);
            } 
            else if (min_from_left && !max_from_left) {
                // Trọng số = minL * maxR * (j - i + 1)
                int term1 = get_mod((sum_maxR_j[R] - sum_maxR_j[L - 1]));
                int term2 = get_mod((sum_maxR[R] - sum_maxR[L - 1]) * (i - 1));
                total = (cur_minL * get_mod(term1 - term2)) % MOD;
            } 
            else {
                // Trọng số = minR * maxL * (j - i + 1)
                int term1 = get_mod((sum_minR_j[R] - sum_minR_j[L - 1]));
                int term2 = get_mod((sum_minR[R] - sum_minR[L - 1]) * (i - 1));
                total = (cur_maxL * get_mod(term1 - term2)) % MOD;
            }
            return total;
        };

        // Gom các khoảng rời nhau từ m+1 đến r tạo bởi các điểm chia p1, p2
        vector<int> borders = {m + 1, p1, p2, r + 1};
        sort(borders.begin(), borders.end());
        borders.erase(unique(borders.begin(), borders.end()), borders.end());

        for (size_t k = 0; k < borders.size() - 1; k++) {
            ans = (ans + query_sum(borders[k], borders[k + 1] - 1)) % MOD;
        }
    }

    return ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];

    cout << divide_and_conquer(1, n) << "\n";

    return 0;
}