#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<limits.h>
#include<utility>
#include<vector>
#include<tuple>
#include <map>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i,n) for(ll i=0;i<n;i++)
#define ALL(A) A.begin(),A.end()





int main() {
    string s;
    vector<ll> a(26);
    cin>>s;
    ll ans=0;
    ll n=s.size();
    for(ll i=s.size()-3;i>=0;i--){
        ll c=s[i]-'a';
        ll C=s[i+2]-'a';
        a[C]++;
        if(s[i]==s[i+1]&&s[i]!=s[i+2]){
            ans+=n-2-i-a[c];
            rep(i,26){
                //cout<<a[i]<<"  ";
                a[i]=0;
            }
            //cout<<endl;
            a[c]=n-2-i;
            //cout<<i<<" "<<ans<<endl;
        }
    }
    cout<<ans<<endl;
}

#include <bits/stdc++.h>          
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repp(i, st, en) for (ll i = (ll)st; i < (ll)(en); i++)
#define repm(i, st, en) for (ll i = (ll)st; i >= (ll)(en); i--)
#define all(v) v.begin(), v.end()
void chmax(ll &x, ll y) {x = max(x,y);}
void chmin(ll &x, ll y) {x = min(x,y);}
void Yes() {cout << "Yes" << endl; exit(0);}
void No() {cout << "No" << endl; exit(0);}
template<class in_Cout> void Cout(in_Cout x) {cout << x << endl; exit(0);}
template<class in_vec_cout>
void vec_cout(vector<in_vec_cout> vec) {
    for (in_vec_cout res : vec) {cout << res << " ";}
    cout << endl;
}

const ll inf = 1e18;
const ll mod = 1e9 + 7;

// segment tree struct
template<class in_seg>
struct segtree {
    in_seg op(in_seg x, in_seg y) {return min(x,y);} // モノイド演算
    in_seg e = inf;       // 元(+→0, *→1, xor→0, max→-inf, min→inf, gcd→0 : e●a==a●e==a)
    ll len = 1LL;     // セグメントの長さ
    ll N;
    vector<in_seg> dat;

    segtree(ll n) {init_seg(n);}
    segtree(vector<in_seg> vec) {init_seg(vec);}

    void init_seg(ll n) {
        N = n;
        while (len<N) {len *= 2;}
        dat.resize(2*len,e);
    }
    void init_seg(vector<in_seg> vec) {
        N = vec.size();
        init_seg(N);
        rep(i,N) dat[i+len] = vec[i];
        for (ll i=len-1; i>=1; i--) dat[i] = op(dat[2*i],dat[2*i+1]);
    }

    // dat[id]に x を代入
    void set(ll id, in_seg x) {
        id += len;
        dat[id] = x;
        while (id>0) {
            id /= 2;
            dat[id] = op(dat[2*id],dat[2*id+1]);
        }
    }

    // dat[id]を返す O(1)
    in_seg get(ll id) {id += len; return dat[id];}

    // op(a[l],...,a[r-1])を計算して返す。l==rの時は e を返す O(logN)
    in_seg prod(ll l, ll r) {
        l += len; r += len;
        in_seg res = e;
        while (l<r) {
            if (l%2) {res = op(res,dat[l]); l++;}
            l /= 2;
            if (r%2) {res = op(res,dat[r-1]); r--;}
            r /= 2;
        }
        return res;
    }

    in_seg all_prod() {return dat[1];}
};

int main() {
    ll N, M; cin >> N >> M;
    vector<ll> A(N);
    rep(i,N) cin >> A[i];

    vector<ll> cnt(N);
    segtree<ll> seg(N+1);
    rep(i,seg.len) seg.set(i,i); 
    rep(i,M) {
        ll a = A[i];
        cnt[a]++;
        seg.set(a,inf);
    }

    ll ans = inf;
    for (ll i=M-1; i<N; i++) {
        chmin(ans,seg.all_prod());
        if (i==N-1) break;
        ll l = A[i-M+1], r = A[i+1];
        cnt[l]--;
        cnt[r]++;
        if (cnt[l]==0) seg.set(l,l);
        seg.set(r,inf);
    }

    Cout(ans);
}