Laiko ribojimas: 2s

Atminties ribojimas: 128MB

Jei norite pateikti savo sprendimą - prisijunkite.

Slenkanti mediana

Vytautas Aldui Kalėdų proga padovanojo seką a_1,a_2,...,a_n, sudarytą iš n (1\\leqn\\leq10^5, 1\\leqa_i\\leq10^9) sveikųjų skaičių. Tačiau kitą dieną Augustinas iš Aldo tą seką pavogė ir pasakė, kad ją grąžins tik tada, kai sugalvos, kaip išspręsti šį uždavinį: kiekvienam k dydžio intervalui sekoje reikia surasti jo medianą. Padėkite Augustinui išspręsti šį uždavinį!

Augustinui Aldas priminė, jog (šiek tiek kitaip, nei matematikos pamokose) sekos mediana vadiname vidurinį jos elementą. Formaliai, n dydžio išrikiuotos sekos b_1,b_2,...,b_n (b_i\\leqb_{i+1}, kai 1\\leqi\\leqn-1) mediana vadinsime \\lceil\\frac{n}{2}\\rceil -ąjį sekos b elementą. Pavyzdžiui, sekos [4,10,18,18] mediana bus 10, o sekos [5,12,1] sekos mediana bus 5. Čia \\lceilx\\rceil reiškia pirmą sveikąjį skaičių, nemažesnį už x. Pavyzdžiui, \\lceil5.5\\rceil=6, \\lceil5.01\\rceil=6, \\lceil6\\rceil=6, \\lceil4\\rceil=4.

Pradiniai duomenys

Pirmoje eilutėje pateikti du tarpais atskirti skaičiai n ir k (1\\leqk\\leqn\\leq10^5). Antrojoje eilutėje pateikta n skaičių a_1,a_2,...,a_n.

Rezultatai

Išveskite n-k+1 tarpais atskirtų sveikųjų skaičių: iš eilės (iš kairės į dešinę) kiekvieno k dydžio intervalo medianą.

Pavyzdžiai

Duomenys Rezultatai Paaiškinimas 
4 4
1 3 2 2
 
2
 Viso masyvo mediana yra tokia pat, kaip išrikiuoto masyvo [1,2,2,3] mediana. 
7 4
1 1 1 2 2 2 3
 
1 1 2 2
  • Pirmasis intervalas [1,1,1,2], jo mediana 1.
  • Antrasis intervalas [1,1,2,2], jo mediana 1.
  • Trečiasis intervalas [1,2,2,2], jo mediana 2.
  • Ketvirtasis intervalas [2,2,2,3], jo mediana 2.
    		•  
    5 3
1 2 2 1 1
    		 
    2 2 1
  • Pirmasis intervalas [1,2,2], jo mediana 2.
  • Antrasis intervalas [2,2,1], jo mediana 2.
  • Trečiasis intervalas [2,1,1], jo mediana 1.
    		•