I believe that size of subarray was >=3 and not >3 in the question,

my solution for >=3 was

void solve() {
    int n;
    cin>>n;
    int a[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
       
    }
    stack<int>s;
    int ans=0;
    for (int i = 0; i < n; ++i)
    {
        if(s.empty()) {
            s.push(a[i]);
        }
        else{
            while(!s.empty() && a[i]>s.top()) {
                ans++;
                s.pop();
            }
            if(s.empty()) {
                ans--;
                s.push(a[i]);
            }
            else if(s.top()!=a[i]) {
                 s.push(a[i]);
            }
           
        }

       
    }
    cout<<ans;
}

.

can you please explain the though process and how ?

This was the solution I came up with, but I am not sure if it's correct. My reasoning was that if we are at position a[i] we are only interested if we have bigger element both to the left and to the right, if that is so we can for sure form an offer (?). That way I preprocess the array so I have prefix and suffix arrays which are :

$$$prefix[i] = max(prefix[i-1], arr[i-1]$$$, and

$$$suffix[i] = max(suffix[i+1], arr[i+1])$$$

I do this, because at each local maximum the condition of having max both to the left and right will fail, and I will be able to "mark" ends. Now consecutive elements that have bigger elements both to the left and to the right form one offer, and every time I break that consecutive property I know I am out of that offer.

Examples I have come up with :

1 2 3 -> 0

5 1 2 3 4 -> 1

10 1 1 10 1 1 9 -> 2, now the last one is controversial, my code outputs 2, but we could debate what's the correct answer to it!

Anyways, here's my code :

#include <vector>
#include <iostream>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    vector<int> prefix(n);
    vector<int> suffix(n);

    int res = 0;

    for (int i = 1; i < n; i++) {
        prefix[i] = max(prefix[i-1], arr[i-1]);
        suffix[n-i-1] = max(suffix[n-i], arr[n-1]);
    }

    bool sw = false;
    for (int i = 0; i < n; i++) {
        if (arr[i] < suffix[i] && arr[i] < prefix[i] && sw == false) {
            sw = true;
            res++;
        }
        else if (!(arr[i] < suffix[i] && arr[i] < prefix[i]) && sw == true){
            sw = false;
        }
    }
    cout << res << endl;
}

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

First of all compresed value of array. each value is maximum n.

Now lets fix the maximum element of inside interval, for all i find maximum j < i such that a[j] > a[i] mark L[i], and find minimum j > i such that a[j] > a[i] mark this with R[i].

Now you know where is ith element is maximum.

Fix the ith, and you need to find how many l > L[i] ^ l < i and r < R[i] ^ r > i such that min(a[l], a[r]) > a[i].

lets consider : left block is interval (L[i], i) right block is interval (i, R[i]) A = how many number from left block such that > a[i] B = how many number from right block such that > a[i]

we are almost done. you only need to sum for all i, A * B.

to find A and B you can do offline fenwick tree, i think that is easier way to do that.

that is all.

correct me if i am wrong.

Can you check if this works?

UPD: This will only work if all the elements are unique.

void solve(int tc) {
    int n; cin >> n;
    vector<int> a(n);
    for(auto &i: a)
        cin >> i;
    int ans = 0;

    auto work = [&](){
        int mx = max(a[0], a[1]);
        for(int i = 2; i < n; i++){
            ans += (a[i] > a[i - 1]);
            ans -= (a[i] > mx);
            mx = max(mx, a[i]);
        }
    };

    work();
    reverse(a.begin(), a.end());
    work();

    cout << ans << '\n';
}

Auto comment: topic has been updated by Venkatesh2112001 (previous revision, new revision, compare).

it's just a simple stack q

~~~~~
void solve() {
    int n; cin >> n;
    vi a(n); cin >> a;
    ll res = 0;
    vi s;
    for(int i = 0; i < n; i++) {
        while(!s.empty() && a[s.back()] < a[i]) s.pop_back();
        if(!s.empty() && i - s.back() + 1 >= 3) res++;
        s.pb(i);
    }
    vi().swap(s);
    for(int i = n — 1; i >= 0; i--) {
        while(!s.empty() && a[s.back()] < a[i]) s.pop_back();
        if(!s.empty() && s.back() - i + 1 >= 3 && a[i] != a[s.back()]) res++;
        s.pb(i);
    }
    cout << res << '\n';
}
~~~~~

#include <bits/stdc++.h>
using namespace std;
#define ll long long
void prints(auto &vec)
{
    for(auto it:vec)
    {
        cout<<it<<" ";
    }
    cout<<endl;
}
signed main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        vector<ll> v(n);
        for(ll i=0;i<n;i++)
        {
            cin>>v[i];
        }
        stack<ll> st;
        st.push(v[0]);
        ll ans=0;
        for(ll i=2;i<n;i++)
        {
            while(!st.empty() && st.top()<v[i-1])
            {
                st.pop();
            }
           while(!st.empty() && min(st.top(),v[i])>v[i-1])
           {
                if(st.top()>v[i])
                {
                    ans+=(int)st.size();
                    break;
                }
                else
                {
                    ans+=1;
                    st.pop();
                }
           }
           st.push(v[i-1]);
        }
        
        cout<<ans<<endl;
    }
    return 0;
}

Here is a straightforward solution in O(nlogn + nlogn) using sparse table and binary search (for subarray size >= 3):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <class T, typename F>
class SparseTable{
public:
    ll n;
    vector<vector<T>> mat;
    F func;
    SparseTable(const vector<T>& a, const F& f) : func(f){
        n = a.size();
        ll max_log = __lg(n + 1) + 1;
        mat.resize(max_log);
        mat[0] = a;
        for (ll j = 1; j < max_log; ++j){
            mat[j].resize(n - (1LL << j) + 1);
            for (ll i = 0; i <= n - (1LL << j); ++i){
                mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1LL << (j - 1))]);
            }
        }
    }
    T get(ll from, ll to) const{
        assert(0 <= from && from <= to && to <= n - 1);
        ll lg = __lg(to - from + 1);
        return func(mat[lg][from], mat[lg][to - (1LL << lg) + 1]);
    }
};
template <typename T, typename F>
SparseTable<T, F> create(const vector<T>& a, F func){
    return SparseTable<T, F>(a, func);
}

void solve(){
    ll n; cin >> n;
    vector<ll> a(n);
    for(auto &x : a) cin >> x;
    auto op = [](ll x, ll y) { return max(x, y); };
    auto st = create(a, op);
    auto left_greater = [&](ll p){
        ll lo = 0, hi = p - 1, ans = -1;
        while(lo <= hi){
            ll mid = (lo + hi) >> 1;
            if(st.get(mid, p - 1) > a[p]){
                ans = mid;          
                lo = mid + 1;      
            } 
            else hi = mid - 1;
        }
        return ans;                
    };
    auto right_greater = [&](ll p){
        ll lo = p + 1, hi = n - 1, ans = -1;
        while(lo <= hi){
            ll mid = (lo + hi) >> 1;
            if(st.get(p + 1, mid) > a[p]){
                ans = mid;         
                hi = mid - 1;      
            } 
            else lo = mid + 1;
        }
        return ans;                
    };
    ll count = 0;
    for(ll p = 0; p < n; ++p){
        ll L = left_greater(p);
        if(L != -1 && p - L + 1 >= 3) ++count;   
        ll R = right_greater(p);
        if(R != -1 && R - p + 1>= 3) ++count;
    }
    cout << count << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    solve();
    return 0;
}

//<------------- !! GANPATI BAPPA MORYA !! ---------------->
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

typedef long long ll;
// #define int long long
//constexpr int INF = 1e18;
const int inf = 1e9;
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define vpi vector<pii>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define yes() cout << "YES\n"
#define no() cout << "NO\n"
#define endl '\n'
#define d3(x,y,z) cout << x << " " << y << " " << z << "\n"
#define d2(x,y) cout << x << " " << y << "\n"
#define d(x) cout << x << "\n"
#define d0(x) cout << x << " "
#define bob() cout << "Bob\n"
#define alice cout << "Alice\n"
#define pb push_back

template<typename T>
istream& operator>>(istream &is, vector<T> &v)
{
    for (auto &x : v) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v)
{
    for (auto &x : v) os << x << ' ';
    return os;
}


#ifndef judge
#define debug(x) ;
#else
#include "debug.h"
#endif

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define NFOR(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define inp(v,n) for(int i = 0;i < n;++i) cin >> v[i];
#define rep(i,n) for(int i = 0;i < n;++i)
#define rep2(i,a,b) for(int i = (a);i < (b);++i)
#define rep3(i,a,b,x) for(int i = (a);i < (b);i += x)

constexpr int mod = 1e9 + 7;
constexpr int MOD = 998244353;

int nextGreater(const vector<int>& A, set<pair<int, int >> & ans, int revert = 0)
{
    int n = A.size();
    stack<int> st;
    int cnt = 0;

    for (int i = 0; i < n; ++i)
    {
        while (!st.empty() && A[i] >= A[st.top()])
        {
            if (abs(i - st.top()) >= 2)
            {
                int x = i;
                int y = st.top();
                if(x > y) swap(x, y);
                if(revert)
                {
                    x = n - i - 1;
                    y = n - st.top() - 1;
                    if(x > y) swap(x, y);
                    ans.insert({x, y});
                }
                else
                {
                    ans.insert({x, y});
                }
                cnt++;
            }
            st.pop();
        }
        st.push(i);
    }

    return cnt;
}

void Solve(int ts = 1)
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<int>fused(n);
    vector<int>bused(n);
    set<pair<int, int >> ans;
    int nv = nextGreater(a, ans, 0);
    reverse(all(a));
    int pv = nextGreater(a, ans, 1);
    cout << ans.size() << "\n";
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef judge
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif

    int _ = 1;
    // cin >> _;
    for(int __ = 1; __ <= _; ++__)
    {
        // cout << "CASE : " << __ << "\n";
        Solve(__);
    }
    return 0;
}

Use the max of the interval l..r as the pivot, then divide and conquer & use a monotone stack?