#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

int main()
{
    int num_hills;
    cin >> num_hills;
    if (num_hills < 3)
    {
        cout << "0\n";
        return 0;
    }

    vector<int> hills;
    vector<int> last_hill_idx(1'000'000, -1);
    uint64_t result = 0;

    int cur_hill;
    for (int i = 0; i < num_hills; i++)
    {
        cin >> cur_hill;
        hills.push_back(cur_hill); 

        if (last_hill_idx[cur_hill] != -1)
        {
            // build bridge
            // cout << "cycle " << i << " adding to result " << i - last_hill_idx[cur_hill] - 1 << "\n";
            result += i - last_hill_idx[cur_hill] - 1;
        }

        // width > height
        if (i - max(0, last_hill_idx[cur_hill]) > cur_hill)
        {
            for (int j = 0; j < cur_hill; j++)
            {
                last_hill_idx[j] = -1;
            }
            
        }
        else
        {
            for (int j = i - 1; j >= 0 && hills[j] < cur_hill; j--)
            {
                last_hill_idx[hills[j]] = -1;
            }
            
        }
        last_hill_idx[cur_hill] = i;

        // for (size_t k = 0; k < 4; k++)        
        // {
        //     cout << last_hill_idx[k] << " ";
        // }
        // cout << "\n";
    }
    
    // cout << "\n";
    cout << result << "\n";


    return 0;
}