Državno natjecanje 2016. / Osnovna škola (8. razred) - 1. zadatak

Razočaran time što se turisti često preguravaju u redu za najbolji primoštenski sladoled, Stipe je odlučio jedan dan provesti promatrajući turiste koji dolaze u red ispred slastičarnice te zapisivati vrijeme njihovog dolaska.

Turisti često prilikom dolaska u slastičarnicu ne staju na kraj reda kako bi trebali, već ulaze u red na nekoj drugoj poziciji.

Stipu zanima koliko je ljudi u redu nezadovoljno.

Osoba X je nezadovoljna ako u redu postoji osoba Y takva da se nalazi ispred osobe X i da je vrijeme dolaska osobe Y strogo veće od vremena dolaska osobe X.

Na temelju Stipinih podataka odredi i ispiši broj nezadovoljnih ljudi u redu.

Napomena: red će u nekim test podacima biti vrlo velik; pripazi na vremensko ograničenje!

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 100 000), broj turista u redu.

U i-tom od sljedećih N redaka nalazi se vrijeme dolaska turista koji se nalazi na i-toj poziciji u redu.

Vremena dolazaka zadana su u standardnom obliku „sat:minuta:sekunda“ sa zapisom od dvije znamenke (npr. 12:54:00, 21:07:28, 06:15:06). Svi turisti dolaze unutar istog dana.

IZLAZNI PODATCI

U jedini redak ispiši broj nezadovoljnih ljudi u redu.

PRIMJERI TEST PODATAKA

Ulaz

3
12:05:01
11:12:59
11:19:33

Izlaz

2

Objašnjenje

Opis prvog test podatka: Osobe na poziciji 2 (11:12:59) i 3 (11:19:33) nezadovoljne su jer je osoba na poziciji 1 (12:05:01) došla kasnije, a stoji ispred njih.

Ulaz

5
00:00:00
00:00:00
00:00:01
23:59:59
23:59:59

Izlaz

0

Ulaz

5
10:05:01
10:12:59
10:10:33
12:50:21
12:30:07

Izlaz

2