/*#pragma GCC optimize("O3") #pragma GCC optimization("Ofast,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")*/ #include <bits/stdc++.h> /*#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>*/ #define ll long long #define ll1 long long #define ull unsigned long long #define dou long double #define str string #define vll vector<ll> #define vi vector<int> #define pll pair<ll, ll> #define vpll vector<pair<ll, ll>> #define vbool vector<bool> #define vstr vector<str> #define vvll vector<vll> #define pb push_back #define pf push_front #define endl "\n" #define fr first #define se second // #define sortcmp(a) sort(a.begin(), a.end(), cmp) #define sort(a) sort(a.begin(), a.end()) #define reverse(a) reverse(a.begin(), a.end()) #define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> using namespace std; //using namespace __gnu_pbds; const ll INF = 1e18+7; const int lg = 20; //const ll MOD = 1e9+7; const ll MOD2 = 998244353; mt19937 rng(1488); ll randll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } vll p, s, mn; ll f(ll v) { if (p[v] == v) return v; return p[v] = f(p[v]); } void unite(ll a, ll b) { a = f(a); b = f(b); if (a == b) return; mn[b] = min(mn[b], mn[a]); mn[a] = min(mn[b], mn[a]); if (s[a] < s[b]) { mn[b] = min(mn[b], mn[a]); p[a] = b; s[b] += s[a]; } else { p[b] = a; s[a] += s[b]; } } vll tree; ll get(ll l, ll r, ll v, ll tl, ll tr) { if (l <= tl && tr <= r) return tree[v]; if (tl > r || tr < l) return -INF; ll tm = (tl+tr)/2; //push(v, tl, tr); ll p = get(l, r, v*2, tl, tm), p1 = get(l, r, v*2+1, tm+1, tr); return max(p,p1); } void update(ll idx, ll val, ll v, ll tl, ll tr) { if (tl == tr) { tree[v] = val; return; } ll tm = (tl+tr)/2; //push(v, tl, tr); if (idx <= tm)update(idx, val, v*2, tl, tm); else update(idx, val, v*2+1, tm+1, tr); tree[v] = max(tree[v*2], tree[v*2+1]); } int main() { speed; ll n, k; cin >> n >> k; p.resize(n+7); s.resize(n+7, 1); mn.resize(n+7); vll a(n); vpll v; for (int i = 0; i < n; i ++) { p[i] = mn[i] = i; cin >> a[i]; v.pb({a[i], i}); } set<ll> st; sort(v); ll k0 = 1; for (int i = 0; i < n; i ++) { if (i != 0 && v[i-1].fr != v[i].fr) k0 ++; a[v[i].se] = k0; } reverse(v); vbool us(n+7, 0); vll pr(n, -1); vpll v_; for (auto i : v) { if (v_.size() && v_[0].fr != i.fr) { for (auto j : v_) { us[j.se] = 1; if (us[j.se+1]) unite(j.se, j.se+1); if (j.se > 0 && us[j.se-1]) unite(j.se, j.se-1); if (s[f(j.se)] >= k) st.insert(mn[f(j.se)]); } v_.clear(); } if (st.lower_bound(i.se) == st.end()) pr[i.se] = n; else pr[i.se] = *st.lower_bound(i.se)+k-1; v_.pb(i); } tree.resize(k0*4+7, 0); vll dp(n, 1); vll c(n+7, -1); vector<set<ll>> v1(n+7); /*for (int i = 0; i < n; i ++) { cout << a[i] << ' '; } cout << endl; for (int i = 0; i < n; i ++) { cout << pr[i] << ' '; } cout << endl;*/ ll maxl = 0; for (int i = 0; i < n; i ++) { /*cout << a[i] << endl; for (int j = 1; j <= k0; j ++) { cout << get(j, j, 1, 0, k0) << ' '; } cout << endl;*/ dp[i] = get(0, a[i]-1, 1, 0, k0)+1; dp[i] = max(dp[i], get(a[i], a[i], 1, 0, k0)); if (c[a[i]] != -1) { v1[pr[c[a[i]]]].erase(c[a[i]]); } update(a[i], dp[i], 1, 0, k0); v1[pr[i]].insert(i); c[a[i]] = i; for (int j : v1[i]) { c[a[j]] = -1; update(a[j], 0, 1, 0, k0); } if (pr[i] == n) maxl = max(maxl, dp[i]); // cout << dp[i] << endl; } cout << maxl << endl; }