Državno natjecanje 2015. / Osnovna škola (7. razred) - 1. zadatak

Mirku je dosadno.

Zamislio je neki niz od N prirodnih brojeva i još jedan prirodan broj K.

Mirku je niz super ako se broj 1 pojavljuje u nizu točno jednom, broj 2 točno dvaput, broj 3 točno triput, ..., broj K točno K puta.

Pomozite Mirku napisati program koji će provjeriti je li njegov niz stvarno super.

Ako je zadani niz super, program treba ispisati riječ "SUPER”, inače treba ispisati najmanji prirodan broj X manji ili jednak K koji se ne pojavljuje točno X puta.

Npr. niz 2, 3, 3, 1, 3, 2 je super jer ima 1 pojavljivanje broja 1, 2 pojavljivanja broja 2 te 3 pojavljivanja broja 3. PAZI: Rješenje koje mnogo puta prolazi po danom nizu prekoračit će vremensko ograničenje za veliki N.

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 2 000 000), duljina niza.

U drugom retku nalazi se niz prirodnih brojeva manjih od 1 000 000, brojevi s kojima se Mirko igra.

U trećem retku nalazi se prirodan broj K (1 ≤ K ≤ 5 000), broj iz teksta zadatka.

IZLAZNI PODATCI

Ako je niz super, treba ispisati poruku "SUPER" (bez navodnika), a ako niz nije super, treba ispisati najmanji broj X koji se ne pojavljuje u nizu točno X puta.

PRIMJERI TEST PODATAKA

Ulaz

3
2 1 2
2

Izlaz

SUPER

Ulaz

4
1 2 3 3
3

Izlaz

2

Ulaz

9
3 3 4 4 1 4 2 3 4
4

Izlaz

2