#include <iostream> 
#include <algorithm>
#include <array>
#include <map>
#include <set>
#include <numeric>

using namespace std;

const int N = 3e5 + 3;
const int INF = 1e9;
typedef long long ll;

int p[N], n, pos[N];
int gl[N], gr[N];
ll ans = 0;

struct SegmentTree{
    struct Node{
        pair<int, int> mx{0, 0};
        pair<int, int> mn{0, 0};
        Node(){}
        Node(int idx){
            mx.second = idx;
            mn.second = idx;
        }

        friend Node merge(const Node &l, const Node &r){
            Node ret;
            // make sure rightmost is chosen?
            if(l.mx.first > r.mx.first){
                ret.mx = l.mx;
            }
            else{
                ret.mx = r.mx;
            }
            if(l.mn.first < r.mn.first){
                ret.mn = l.mn;
            }
            else{
                ret.mn = r.mn;
            }
            return ret;
        }
    } nd[4 * N];
    int lp[4 * N];

    void init(int i = 0, int l = 0, int r = n){
        if(l == r){
            nd[i] = Node(l);
            return;
        }

        int mid = (l + r) >> 1;
        init(2 * i + 1, l, mid);
        init(2 * i + 2, mid + 1, r);
        nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
    }

    void push(int i, int l, int r){
        if(!lp[i]) return;

        nd[i].mx.first += lp[i];
        nd[i].mn.first += lp[i];
        if(l != r){
            lp[2 * i + 1] += lp[i];
            lp[2 * i + 2] += lp[i];
        }
        lp[i] = 0;
    }

    void update(int sl, int sr, int val, int i = 0, int l = 0, int r = n){
        push(i, l, r);
        if(r < sl || sr < l) return;
        if(sl <= l && r <= sr){
            lp[i] += val;
            push(i, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        update(sl, sr, val, 2 * i + 1, l, mid);
        update(sl, sr, val, 2 * i + 2, mid + 1, r);
        nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]);
    }

    pair<int, int> get_max(int sl, int sr, int i = 0, int l = 0, int r = n){
        if(sl > sr) return {-1, -1};
        push(i, l, r);
        if(r < sl || sr < l) return {-1, -1};
        if(sl <= l && r <= sr) return nd[i].mx;

        int mid = (l + r) >> 1;
        auto l_ans = get_max(sl, sr, 2 * i + 1, l, mid);
        auto r_ans = get_max(sl, sr, 2 * i + 2, mid + 1, r);
        return max(l_ans, r_ans);
    }

    pair<int, int> get_min(int sl, int sr, int i = 0, int l = 0, int r = n){
        if(sl > sr) return {INF, INF};
        push(i, l, r);
        if(r < sl || sr < l) return {INF, INF};
        if(sl <= l && r <= sr) return nd[i].mn;

        int mid = (l + r) >> 1;
        auto l_ans = get_min(sl, sr, 2 * i + 1, l, mid);
        auto r_ans = get_min(sl, sr, 2 * i + 2, mid + 1, r);
        return min(l_ans, r_ans);
    }
} st;

void calc_answer(){
    static int cnt2[2 * N];
    int *cnt = cnt2 + N;
    for(int i = 1; i <= n; ++i){
        cout << i << " i" << endl;
        int sum = 0;
        ++cnt[0];
        for(int j = pos[i] - 1; j > gl[i]; --j){
            int val = (p[j] > i) ? 1 : -1;
            sum += val;
            ++cnt[sum];
        }

        sum = 0;
        ans += ((ll)i) * (cnt[-sum] + cnt[-sum + 1]);
        for(int j = pos[i] + 1; j <= gr[i]; ++j){
            int val = (p[j] > i) ? 1 : -1;
            sum += val;
            ans += ((ll)i)*(cnt[-sum] + cnt[-sum + 1]);
        }

        {
            int sum = 0;
            --cnt[0];
            for(int j = pos[i] - 1; j > gl[i]; --j){
                int val = (p[j] > i) ? 1 : -1;
                sum += val;
                --cnt[sum];
            }
        }
    }
    cout << ans << "\n";
}

void calc_ranges(){
    st.init();
    for(int i = 1; i <= n; ++i)
        st.update(i, n, 1);

    for(int i = 1; i <= n / 2; ++i){
        st.update(pos[i], n, -1);

        auto [mn, idx_mn] = st.get_min(pos[i], n);
        auto [mn2, idx_mn2] = st.get_min(0, pos[i]);
        gl[i] = idx_mn - 1;
        gr[i] = idx_mn;

        st.update(pos[i], n, -1);
    }

    for(int i = n / 2 + 1; i <= n; ++i){
        st.update(pos[i], n, -1);

        auto [mx, idx_mx] = st.get_max(pos[i], n);
        auto [mx2, idx_mx2] = st.get_max(0, pos[i]);
        gl[i] = idx_mx2 - 1;
        gr[i] = idx_mx;

        st.update(pos[i], n, -1);
    }

    for(int i = 1; i <= n; ++i){
        // cout << gl[i] << " " << gr[i] << endl;
        // gl[i] = 0, gr[i] = n;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> p[i];
        pos[p[i]] = i;
    }

    cout << "before " << endl;
    calc_ranges();
    cout << "ranges" << endl;
    calc_answer();
}