#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{
        int mn, mx;
        Node(){
            mn = INF;
            mx = -INF;
        }
        Node(int idx){
            mn = mn = 0;
        }

        friend Node merge(const Node &l, const Node &r){
            Node ret;
            ret.mn = min(l.mn, r.mn);
            ret.mx = max(l.mx, r.mx);
            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 += lp[i];
        nd[i].mn += 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]);
    }

    Node query(int sl, int sr, int i = 0, int l = 0, int r = n){
        // if(sl > sr) return Node();
        push(i, l, r);
        if(r < sl || sr < l) return Node();
        if(sl <= l && r <= sr) return nd[i];

        int mid = (l + r) >> 1;
        auto l_ans = query(sl, sr, 2 * i + 1, l, mid);
        auto r_ans = query(sl, sr, 2 * i + 2, mid + 1, r);
        return merge(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;
        // cout << pos[i] << " pos" << endl;
        // cout << gl[i] << " " << gr[i] << " gl gr" << endl;
        // cout << ans << " before" << 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 << " after" << endl;
    }
    cout << ans << "\n";
}

int get_g(int pos, bool dir, bool mx){
    SegmentTree::Node nd;
    if(dir == true){
        nd = st.query(pos, n);
    }
    else{
        nd = st.query(0, pos - 1);
    }

    int l, r;
    if(dir == true){
        l = 0, r = pos;
    }
    else{
        l = pos - 1, r = n;
    }

    while(l != r){
        int mid;
        if(dir) mid = (l + r) >> 1;
        else mid = (l + r + 1) >> 1;

        SegmentTree::Node node_mid;
        if(dir == true){
            node_mid = st.query(0, mid);
        }
        else{
            node_mid = st.query(mid, n);
        }

        bool ok;
        if(mx == true){
            ok = (node_mid.mx + nd.mx) >= 0;
        }
        else{
            ok = (node_mid.mn + nd.mn) <= 1;
        }

        if(dir){
            if(ok){
                r = mid;
            }
            else{
                l = mid + 1;
            }
        }
        else{
            if(ok){
                l = mid;
            }
            else{
                r = mid - 1;
            }
        }
    }

    return l;
}

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);

        gl[i] = get_g(pos[i], true, false);
        gr[i] = get_g(pos[i], false, false);

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

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

        gl[i] = get_g(pos[i], true, true);
        gr[i] = get_g(pos[i], false, true);

        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();
}