Državno natjecanje iz informatike 2019. / Prva podskupina (1. i 2. razred) - 2. zadatak

Noa je dobio ozbiljan zadatak. On i njegova mornarska družina moraju prevesti N životinja na daleki otok.

Znajući da neće moći oka sklopiti ako povede više životinja iste vrste jer će se one neprestano svađati, odlučio je povesti najviše po jednu životinju svake vrste na jedan brod.

Životinje su poredane u niz te su njihove vrste označene s A1, A2, … AN, a oznaka svake vrste prirodan je broj između 1 i M.

Radi jednostavnosti ukrcaja Noa je odlučio da će na svaki brod ići neki uzastopni podniz životinja u nizu.

Kako je ovakvo putovanje opasno, Nou zanima najmanji mogući broj brodova koji mogu prevesti sve životinje na opisani način.

Nažalost, Noinim problemima tu nije kraj.

U starosti mu se pokvario i vid pa nije siguran je li dobro raspoznao sve životinje.

No, vjeruje da nije pogriješio u raspoznavanju više od jedne životinje.

Sada ga, za Q različitih scenarija oblika “ako je životinja na poziciji P u nizu zapravo vrste Z”, zanima koliki je najmanji broj brodova koji bi mu u tom slučaju trebao.

(Ovi scenariji ne nadovezuju se jedan na drugi.) Pomozite starom Noi odgovoriti na njegova pitanja.

Ulazni podaci

U prvom su retku prirodni brojevi N, M i Q (1 ≤ N, M, Q ≤ 500 000), broj životinja, broj različitih vrsta i broj upita.

U idućem retku nalazi se niz od N prirodnih brojeva A1, A2, … AN (1 ≤ Ai ≤ M), vrste životinja u nizu.

U idućih Q redaka nalaze se po dva prirodna broja Pq (1 ≤ Pq ≤ N) i Zq (1 ≤ Zq ≤ M) iz teksta zadatka.

Broj Zq razlikuje se od trenutačnog broja na poziciji Pq.

Izlazni podaci

Ispišite Q brojeva, svaki u svojem retku, koji označavaju tražene odgovore na pitanja redom kojim su dana u ulazu.

Primjer zadatka

Ulaz

7 4 3
1 2 1 2 1 3 4
3 2
3 3
7 1

Izlaz

3
2
4

Objašnjenje

Pojašnjenje prvog primjera: Dobiveni nizovi i odgovarajući rastavi na brodove:

Ulaz

10 6 4
1 2 3 4 5 5 4 3 2 1
4 2
5 1
6 3
6 6

Izlaz

3
3
3
2