$O(N)$ 单调栈

基本观察：

所有单元素子数组都满足条件（因为首尾都是自己）

对于多元素子数组，只有当首尾元素相等且是该子数组的最大值时才能满足条件

关键思路：

使用单调栈来维护一个递减序列

统计每个元素作为最大值时能形成的有效子数组

使用哈希表记录当前栈中各个数值的出现次数

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

#define x first
#define y second

const int N = 2e5 + 10, M = 30;

int n;
int a[N];

void solve() 
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    
    int ans = n;
    stack<int> stk;
    map<int, int> cnt;
    for(int i = 1; i <= n; i ++)
    {
        while(stk.size() && a[stk.top()] < a[i])
        {
            cnt[a[stk.top()]] --;
            stk.pop();
        }
        
        ans += cnt[a[i]];
        stk.push(i);
        cnt[a[i]] ++;
    }
    cout << ans << endl;
    
}            

int main()
{
    int t = 1;
    cin >> t;
    while(t --)
        solve();
}