using namespace std;

typedef long long ll;

const int MAXN = 1001000; int fenwickTree[MAXN], n; vector addLater[MAXN];

inline int getPrefixSum(int idx) { int sum = 0; while (idx >= 0) { sum += fenwickTree[idx]; idx = (idx & (idx + 1)) - 1; } return sum; }

inline void update(int idx, int delta) { while (idx < n) { fenwickTree[idx] += delta; idx = (idx | (idx + 1)); } }

ll solve(vector& arr) { vector nextGreater(sz(arr)), prevSmaller(sz(arr)); vector st;

// Calculate previous smaller elements
for (int i = sz(arr) - 1; i >= 0; --i) {
    while (!st.empty() && arr[st.back()] >= arr[i])
        st.pop_back();
    prevSmaller[i] = st.empty() ? -1 : st.back();
    st.push_back(i);
}

// Clear stack for next greater elements
st.clear();

// Calculate next greater elements
forn(i, sz(arr)) {
    while (!st.empty() && arr[st.back()] <= arr[i])
        st.pop_back();
    nextGreater[i] = st.empty() ? sz(arr) : st.back();
    st.push_back(i);
}

// Prepare for updates
forn(i, sz(prevSmaller)) {
    if (prevSmaller[i] != -1)
        addLater[prevSmaller[i] + 1].push_back(i);
}

ll result = 0;
forn(i, sz(arr)) {
    for (int idx : addLater[i])
        update(idx, 1);
    if (nextGreater[i] != sz(arr))
        result += getPrefixSum(nextGreater[i] - 1) - getPrefixSum(i - 1);
}

return result;

}

int main() { n = readInt(1, MAXN); vector arr(n); forn(i, n) { arr[i] = readInt(1, n) - 1; } cout << solve(arr) << endl; return 0; }