DRŽAVNO NATJECANJE 2014. - Prvi dan natjecanja / Srednja škola, I. podskupina (1. i 2. razred) - 3. zadatak

Medijan niza (ne nužno različitih) prirodnih brojeva definiramo kao srednji element u nizu koji se dobije njegovim sortiranjem.

Ukoliko je niz parne duljine, tada medijanom smatramo manji od dva srednja broja nakon sortiranja.

Na primjer, medijani nizova (1), (1, 3), (4, 5, 4), (4, 1, 2, 3) i (5, 4, 1, 2, 3) su redom 1, 1, 4, 2 i 3.

Ako je zadan niz X koji se sastoji od N prirodnih brojeva i prirodni broj K, odredi broj podnizova uzastopnih elemenata zadanog niza čiji je medijan barem K.

Ulazni podaci

U prvom redu nalaze se dva prirodna broja N i K (1 ≤ N ≤ 200 000, 1 ≤ K ≤ 1 000 000).

U svakom od sljedećih N redova nalazi se po jedan prirodni broj Xi (1 ≤ Xi ≤ 1 000 000), elementi niza X.

Izlazni podaci

U prvi i jedini redak ispišite jedan cijeli broj, broj podnizova čiji je medijan barem K.

Primjer zadatka

Ulaz

4 3
1
1
3
4

Izlaz

4

Objašnjenje

Pojašnjenje prvog test primjera: Svi mogući podnizovi uzastopnih elemenata zadanog niza i njihovi medijani su redom:

Ulaz

6 7
8
7
3
2
2
7

Izlaz

5

Ulaz

10 5
1
10
2
9
3
8
4
7
5
6

Izlaz

29