/// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
/// Training ICPC 2024
#include<bits/stdc++.h>
/// #pragma GCC optimize("O3,unroll-loops")
/// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define fi first
#define se second
#define TASK "test"
#define pb push_back
#define EL cout << endl
#define Ti20_ntson int main()
#define in(x) cout << x << endl
#define all(x) (x).begin(),(x).end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define cntbit(x) __builtin_popcount(x)
#define FOR(i,l,r) for (int i = l; i <= r; i++)
#define FORD(i,l,r) for (int i = l; i >= r; i--)
#define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> vii;
typedef unsigned long long ull;
typedef vector<vector<int>> vvi;
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
const int N = 1e6 + 5;
const int oo = INT_MAX;
const int mod = 1e9 + 7;
const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int n, a[N], k;
inline void Read_Input() {
cin >> n >> k;
FOR(i, 1, n)
cin >> a[i];
}
struct Segment_Tree {
int st[4 * N + 5];
void build(int id, int l, int r) {
memset(st, 0x3f, sizeof(st));
}
void update(int id, int l, int r, int u, int v, int val) {
if (l > v || r < u)
return;
if (l >= u && r <= v) {
st[id] = min(st[id], val);
return;
}
int mid = (l + r) >> 1;
update(id * 2, l, mid, u, v, val);
update(id * 2 + 1, mid + 1, r, u, v, val);
st[id] = min(st[id * 2], st[id * 2 + 1]);
}
int Get(int id, int l, int r, int u, int v) {
if (l > v || r < u)
return mod;
if (l >= u && r <= v)
return st[id];
int mid = (l + r) >> 1;
return min(Get(id * 2, l, mid, u, v), Get(id * 2 + 1, mid + 1, r, u, v));
}
}it;
inline void Solve() {
int Ans = INT_MAX;
vector<int> b(n + 5, 0), pre(n + 5, 0);
// FOR(i, 1, n) {
int l = 1, r = 100000;
while (l <= r) {
int T = (l + r) >> 1;
// T = 1;
FOR(j, 1, n)
if (a[j] <= T)
b[j] = 1;
else b[j] = -1;
FOR(j, 1, n)
pre[j] = pre[j - 1] + b[j];
/// cay IT ko xu li cho so am .
/// [-n, n] => Cong n len de thanh so duong [0, 2 * n]
it.build(1, 0, 2 * n);
/// pre[0]
/// chat nhi phan dap an vi no cang nho cang tot
bool oke = false;
FOR(R, 1, n) {
/// hien tai anh vi tri R va so huu pre[R]
it.update(1, 0, 2 * n, pre[R - 1] + n, pre[R - 1] + n, R);
/// pre[L - 1] <= pre[R]
/// pre[L - 1] = (-n, pre[R]);
/// get min vi tri cua khoang nay
/// Don gian bang cay IT;
/// pre[R] - pre[L - 1] >= 0
int L = it.Get(1, 0, 2 * n, 0, pre[R] + n);
if (R - L + 1 >= k) {
/// suy ra a[i] la 1 dap an co the co
oke = true;
break;
}
/// trong tuong lai R1 co the so huu pre[R1] - pre[R - 1] >= 0
/// R1 - R + 1 >= k
/// Do do ta can update vi tri cua pre[R - 1] lai
}
if (oke == true) {
/// T da duoc cong nhan
Ans = T;
r = T - 1;
}
else l = T + 1;
// return;
}
cout << Ans;
}
Ti20_ntson {
// freopen(TASK".INP","r",stdin);
// freopen(TASK".OUT","w",stdout);
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
// cin >> T;
while (T -- ) {
Read_Input();
Solve();
}
}
#include <iostream>
using namespace std;
int main() {
// your code goes here
return 0;
}
Ly8vIEF1dGhvciA6IE5ndXnhu4VuIFRow6FpIFPGoW4gLSBLMTggLSBLSE1UIC0gVUlUCi8vLyBUcmFpbmluZyBJQ1BDIDIwMjQKCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CgovLy8gI3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk8zLHVucm9sbC1sb29wcyIpCi8vLyAjcHJhZ21hIEdDQyB0YXJnZXQoImF2eDIsYm1pLGJtaTIsbHpjbnQscG9wY250IikKCiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKI2RlZmluZSBUQVNLICJ0ZXN0IgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIEVMIGNvdXQgPDwgZW5kbAojZGVmaW5lIFRpMjBfbnRzb24gaW50IG1haW4oKQojZGVmaW5lIGluKHgpIGNvdXQgPDwgeCA8PCBlbmRsCiNkZWZpbmUgYWxsKHgpICh4KS5iZWdpbigpLCh4KS5lbmQoKQojZGVmaW5lIGdldGJpdCh4LCBpKSAoKCh4KSA+PiAoaSkpICYgMSkKI2RlZmluZSBjbnRiaXQoeCkgX19idWlsdGluX3BvcGNvdW50KHgpCiNkZWZpbmUgRk9SKGksbCxyKSBmb3IgKGludCBpID0gbDsgaSA8PSByOyBpKyspCiNkZWZpbmUgRk9SRChpLGwscikgZm9yIChpbnQgaSA9IGw7IGkgPj0gcjsgaS0tKQojZGVmaW5lIERlYnVnKGEsbikgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSBjb3V0IDw8IGFbaV0gPDwgIiAiOyBjb3V0IDw8IGVuZGwKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiBwYWlyPGludCxpbnQ+IHZpaTsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwp0eXBlZGVmIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gdnZpOwppbnQgZmFzdE1heChpbnQgeCwgaW50IHkpIHsgcmV0dXJuICgoKHkteCk+PigzMi0xKSkmKHheeSkpXnk7IH0KCmNvbnN0IGludCBOID0gMWU2ICsgNTsKY29uc3QgaW50IG9vID0gSU5UX01BWDsKY29uc3QgaW50IG1vZCA9IDFlOSArIDc7CmNvbnN0IGludCBkNHhbNF0gPSB7LTEsIDAsIDEsIDB9ICwgZDR5WzRdID0gezAsIDEsIDAsIC0xfTsKY29uc3QgaW50IGQ4eFs4XSA9IHstMSwgLTEsIDAsIDEsIDEsIDEsIDAsIC0xfSwgZDh5WzhdID0gezAsIDEsIDEsIDEsIDAsIC0xLCAtMSwgLTF9OwoKaW50IG4sIGFbTl0sIGs7CgppbmxpbmUgdm9pZCBSZWFkX0lucHV0KCkgewogICAgY2luID4+IG4gPj4gazsKICAgIEZPUihpLCAxLCBuKQogICAgICAgIGNpbiA+PiBhW2ldOwp9CgpzdHJ1Y3QgU2VnbWVudF9UcmVlIHsKICAgIGludCBzdFs0ICogTiArIDVdOwoKICAgIHZvaWQgYnVpbGQoaW50IGlkLCBpbnQgbCwgaW50IHIpIHsKICAgICAgICBtZW1zZXQoc3QsIDB4M2YsIHNpemVvZihzdCkpOwogICAgfQoKICAgIHZvaWQgdXBkYXRlKGludCBpZCwgaW50IGwsIGludCByLCBpbnQgdSwgaW50IHYsIGludCB2YWwpIHsKICAgICAgICBpZiAobCA+IHYgfHwgciA8IHUpCiAgICAgICAgICAgIHJldHVybjsKICAgICAgICBpZiAobCA+PSB1ICYmIHIgPD0gdikgewogICAgICAgICAgICBzdFtpZF0gPSBtaW4oc3RbaWRdLCB2YWwpOwogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogICAgICAgIGludCBtaWQgPSAobCArIHIpID4+IDE7CiAgICAgICAgdXBkYXRlKGlkICogMiwgbCwgbWlkLCB1LCB2LCB2YWwpOwogICAgICAgIHVwZGF0ZShpZCAqIDIgKyAxLCBtaWQgKyAxLCByLCB1LCB2LCB2YWwpOwogICAgICAgIHN0W2lkXSA9IG1pbihzdFtpZCAqIDJdLCBzdFtpZCAqIDIgKyAxXSk7CiAgICB9CgoKICAgIGludCBHZXQoaW50IGlkLCBpbnQgbCwgaW50IHIsIGludCB1LCBpbnQgdikgewogICAgICAgIGlmIChsID4gdiB8fCByIDwgdSkKICAgICAgICAgICAgcmV0dXJuIG1vZDsKICAgICAgICBpZiAobCA+PSB1ICYmIHIgPD0gdikKICAgICAgICAgICAgcmV0dXJuIHN0W2lkXTsKICAgICAgICBpbnQgbWlkID0gKGwgKyByKSA+PiAxOwogICAgICAgIHJldHVybiBtaW4oR2V0KGlkICogMiwgbCwgbWlkLCB1LCB2KSwgR2V0KGlkICogMiArIDEsIG1pZCArIDEsIHIsIHUsIHYpKTsKICAgIH0KCn1pdDsKCmlubGluZSB2b2lkIFNvbHZlKCkgewogICAgaW50IEFucyA9IElOVF9NQVg7CiAgICB2ZWN0b3I8aW50PiBiKG4gKyA1LCAwKSwgcHJlKG4gKyA1LCAwKTsKLy8gICAgRk9SKGksIDEsIG4pIHsKICAgIGludCBsID0gMSwgciA9IDEwMDAwMDsKICAgIHdoaWxlIChsIDw9IHIpIHsKICAgICAgICBpbnQgVCA9IChsICsgcikgPj4gMTsKLy8gICAgICAgIFQgPSAxOwogICAgICAgIEZPUihqLCAxLCBuKQogICAgICAgICAgICBpZiAoYVtqXSA8PSBUKQogICAgICAgICAgICAgICAgYltqXSA9IDE7CiAgICAgICAgICAgIGVsc2UgYltqXSA9IC0xOwogICAgICAgIEZPUihqLCAxLCBuKQogICAgICAgICAgICBwcmVbal0gPSBwcmVbaiAtIDFdICsgYltqXTsKICAgICAgICAvLy8gY2F5IElUIGtvIHh1IGxpIGNobyBzbyBhbSAuCiAgICAgICAgLy8vIFstbiwgbl0gID0+IENvbmcgbiBsZW4gZGUgdGhhbmggc28gZHVvbmcgWzAsIDIgKiBuXQogICAgICAgIGl0LmJ1aWxkKDEsIDAsIDIgKiBuKTsKICAgICAgICAvLy8gcHJlWzBdCiAgICAgICAgLy8vIGNoYXQgbmhpIHBoYW4gZGFwIGFuIHZpIG5vIGNhbmcgbmhvIGNhbmcgdG90CiAgICAgICAgYm9vbCBva2UgPSBmYWxzZTsKICAgICAgICBGT1IoUiwgMSwgbikgewogICAgICAgICAgICAvLy8gaGllbiB0YWkgYW5oIHZpIHRyaSBSIHZhIHNvIGh1dSBwcmVbUl0KICAgICAgICAgICAgaXQudXBkYXRlKDEsIDAsIDIgKiBuLCBwcmVbUiAtIDFdICsgbiwgcHJlW1IgLSAxXSArIG4sIFIpOwogICAgICAgICAgICAvLy8gcHJlW0wgLSAxXSA8PSBwcmVbUl0KICAgICAgICAgICAgLy8vIHByZVtMIC0gMV0gPSAoLW4sIHByZVtSXSk7CiAgICAgICAgICAgIC8vLyBnZXQgbWluIHZpIHRyaSBjdWEga2hvYW5nIG5heQogICAgICAgICAgICAvLy8gRG9uIGdpYW4gYmFuZyBjYXkgSVQ7CiAgICAgICAgICAgIC8vLyBwcmVbUl0gLSBwcmVbTCAtIDFdID49IDAKCiAgICAgICAgICAgIGludCBMID0gaXQuR2V0KDEsIDAsIDIgKiBuLCAwLCBwcmVbUl0gKyBuKTsKICAgICAgICAgICAgaWYgKFIgLSBMICsgMSA+PSBrKSB7CiAgICAgICAgICAgICAgICAvLy8gc3V5IHJhIGFbaV0gbGEgMSBkYXAgYW4gY28gdGhlIGNvCiAgICAgICAgICAgICAgICBva2UgPSB0cnVlOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIC8vLyB0cm9uZyB0dW9uZyBsYWkgUjEgY28gdGhlIHNvIGh1dSBwcmVbUjFdIC0gcHJlW1IgLSAxXSA+PSAwCiAgICAgICAgICAgIC8vLyBSMSAtIFIgKyAxID49IGsKICAgICAgICAgICAgLy8vIERvIGRvIHRhIGNhbiB1cGRhdGUgdmkgdHJpIGN1YSBwcmVbUiAtIDFdIGxhaQoKICAgICAgICB9CgogICAgICAgIGlmIChva2UgPT0gdHJ1ZSkgewogICAgICAgICAgICAvLy8gVCBkYSBkdW9jIGNvbmcgbmhhbgogICAgICAgICAgICBBbnMgPSBUOwogICAgICAgICAgICByID0gVCAtIDE7CiAgICAgICAgfQogICAgICAgIGVsc2UgbCA9IFQgKyAxOwovLyAgICAgICAgcmV0dXJuOwoKICAgIH0KICAgIGNvdXQgPDwgQW5zOwp9CgpUaTIwX250c29uIHsKLy8gICAgZnJlb3BlbihUQVNLIi5JTlAiLCJyIixzdGRpbik7Ci8vICAgIGZyZW9wZW4oVEFTSyIuT1VUIiwidyIsc3Rkb3V0KTsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBjaW4udGllKDApOyBjb3V0LnRpZSgwKTsKICAgIGludCBUID0gMTsKLy8gICAgY2luID4+IFQ7CiAgICB3aGlsZSAoVCAtLSApIHsKICAgICAgICBSZWFkX0lucHV0KCk7CiAgICAgICAgU29sdmUoKTsKICAgIH0KfQoKCiNpbmNsdWRlIDxpb3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJcmV0dXJuIDA7Cn0=