Прыжки по зданиям (C++)

[cppc]

В городе есть n зданий с высотами h1; h2; ...; hn. Мальчик любит прыгать по зданиям и может прыгнуть из одного здания на другое только тогда, когда их высоты одинаковы и высоты всех зданий между ними не превышает высоты текущего здания.
Вам нужно посчитать количество таких пар зданий, которые мальчик может перепрыгнуть с одного дома на другой.

Входные данные:
В первой строке записано целое число n (n ≤ 3 * 10^5). Во второй строке записаны n целых чисел h1; h2 ...; hn (1 ≤ hi ≤ 10^6).

Входные данные:
Выведите единственное целое число - ответ на задачу.

Пример 1:
Ввод
6
3 2 1 2 3 3
Вывод
8

Пример 2:
Ввод
3
1 1000 1
Вывод
0

В примере 1 каждая из следующих пар считается в ответе два раза (в прямом и перевернутом порядке): (1, 5); (1, 6); (5, 6); (2, 4).

Задание нужно решить с использованием дерева отрезков, иначе не пройдет по времени.

Начал чтото делать:

//Задание на дерево отрезков
#include <iostream>
#include <cstring>
#define N 300003
using namespace std;
long long a[N], t[4 * N];
 
//Построение дерева отрезков
void build (long long a[], int v, int tl, int tr) {
    if (tl == tr) t[v] = a[tl];
    else
    {
        int tm = (tl + tr) / 2;
        build (a, v*2, tl, tm);
        build (a, v*2+1, tm+1, tr);
    }
}
 
int number_of_pairs (int v, int tl, int tr)
{
    //TODO
}
 
long long n, l, r, i, j, x;
int main ()
{
    memset(t,0,sizeof(t));
    cin >> n;
    for(j = 1; j <= n; j++) {cin >> x; a[j]=x;}
    build(a, 1, 1, n);
    cout << number_of_pairs(1,1,n) << endl;
    return 0;
}

Подскажите части псевдокодов дерева отрезков, которые нужно использовать при решени задания?

Вот мой вариант решения перебором:

#include <iostream>
#include <vector>
//#define MAXN 1000001
//#define MAXX 1000001
#define _ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
vector<int> v;
int func(vector <int> V)
{
    int q = 0;
    for (int i1 = 0; i1<V.size()-1; i1++)
    {
        for (int i2 = i1+1; i2<V.size(); i2++)
        {
            if (V[i1] == V[i2])
            {
                for (int i3 = 0; i3<V.size()-1; i3++)
                {
                    if (V[i1]>V[i3]) {q+=2; break;}
                }
            }
        }
    }
return q;
}
int main ()
{_
    int n, i, x;
    cin >> n;
    //v.resize(n);
    for (i = 0; i < n; i++)
    {
        cin >> x;
        v.push_back(x);
    }
    cout<<func(v)<<endl;
    return 0;
}

По моему, вариант перебором, не учитывает ситуацию, когда два здания одинаковой высоты находятся рядом и между ними нету других зданий.
Можете подправить код?

Проверте следующие тесты:

Тест #1.
2
6 6
Можно перепрыгнуть: (1, 2); Ответ 2. (Но выводится 0).

Тест #2.
6
5 4 3 3 4 5
Можно перепрыгнуть: (1, 6); (2, 5); (3, 4). Ответ 6. (Но выводится 4).

Тест #3.
6
3 4 5 5 4 3
Можно перепрыгнуть: (3, 4); Ответ 2. (Но выводится 4).

Гляньте пожалуйста.

[cppc]

Думаю, для каждого здания деревом отрезков найти следующее по высоте справа. А потом посчитать сколько таких же зданий на этом отрезке. Но как это сделать програмно? Какие части псевдокодов дерева отрезков нужно использавать?