Answer is here!

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
const int MOD = 998244353;
int n, m, a[N], x, y;
ll ans;
set<int> st;
// 统计没有关键点的方案数
void Calc(int len, int k) { 
    if(len >= m) x += k * (len - m + 1);
}
// 统计只有一个关键点的方案数，it 是这个关键点
void Get(set<int>::iterator it, int k) { 
    if(*it < 1 || *it > n) return ;
    int l = *prev(it), p = *it, r = *next(it);
    if(r - l - 1 < m) return ;
    int lef = max(l + 1, p - m + 1);
    int rig = min(p, r - m);
    y += k * (rig - lef + 1);
}
void Add(int k) {
    auto it = st.lower_bound(k);
    int l = *prev(it), r = *it;
    Calc(r - l - 1, -1), Get(prev(it), -1);
    Calc(k - l - 1, 1), Get(it, -1);
    Calc(r - k - 1, 1);
    st.insert(k);
    it = st.find(k);
    Get(prev(it), 1);
    Get(next(it), 1);
    Get(it, 1);
}
void Del(int k) {
    auto it = st.find(k);
    int l = *prev(it), r = *next(it);
    Calc(r - l - 1, 1), Get(prev(it), -1);
    Calc(k - l - 1, -1), Get(next(it), -1);
    Calc(r - k - 1, -1), Get(it, -1);
    auto tl = prev(it), tr = next(it);
    st.erase(it);
    Get(tl, 1), Get(tr, 1);
}
void Solve() {
    cin >> n, m = n / 2;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    st.insert(0), st.insert(n + 1);
    x = m + 1;
    for(int i = 1; i <= m; ++i) 
        Add(a[i]);
    for(int i = m; i <= n; ++i) {
        ans += 1ll * x * m * (m - 1) + y;
        if(i != n) {
            Add(a[i + 1]);
            Del(a[i - m + 1]);
        }
    }
    printf("%lld\n", ans);
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1; //cin >> t;
    while(t--) Solve();
    return 0;
}
# Thank you very much!