#pragma GCC target("avx512f,avx512dq,avx512vl,prefer-vector-width=512")
#pragma GCC optimize("Ofast,unroll-loops")
//#include <immintrin.h>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); i++)

mt19937 rnd;
using u16 = uint16_t;
using u32 = uint32_t;
u16 N, M;
u16 P[1 << 16];
constexpr int W = 32;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    N = 50000;
    M = 3;
    rep(i, 0, N) P[i] = i + 1;
    shuffle(P, P + N, rnd);
    u16 Ms[W] = {};
    rep(i, 0, W) Ms[i] = M;

    u32 ans = 0;
    int ii = 1;
    for(; ii + W < N - M; ii += W) {
        // 幅 ii から幅 ii + 31 まで
        u16 cnt[W] = {};
        u16 add[W] = {};
        int i = ii;
        for(; i + W <= N; i++) {
            u16 L[W], R[W];
            rep(j, 0, W) L[j] = P[i - ii];
            rep(j, 0, W) R[j] = P[ii + j];
            rep(j, 0, W) {
                // 幅 ii + j
                if(L[j] < R[j]) {
                    cnt[j]++;
                } else {
                    cnt[j] = 0;
                }
            }
            rep(j, 0, W) if(cnt[j] >= Ms[j]) {
                add[j]++;
            }
        }
        for(; i < N; i++) {
            u16 L[W], R[W];
            rep(j, 0, W) L[j] = P[i - ii];
            rep(j, 0, W) {
                if(ii + j >= N) break;
                R[j] = P[ii + j];
            }
            rep(j, 0, W) {
                if(ii + j >= N) break;
                // 幅 ii + j
                if(L[j] < R[j]) {
                    cnt[j]++;
                    if(cnt[j] >= Ms[j]) {
                        add[j]++;
                    }
                } else {
                    cnt[j] = 0;
                }
            }
        }
        for(auto x : add) ans += x;
    }
    for(; ii <= N - M; ii++) {
        // 幅 ii
        u16 cnt = 0;
        rep(j, ii, N) {
            if(P[j - ii] < P[j]) {
                cnt++;
            } else {
                cnt = 0;
            }
            if(cnt >= M) ans++;
        }
    }
    cout << ans << endl;
}