Državno natjecanje 2014. / Osnovna škola (7. razred) - 2. zadatak

Vanzemaljci nemaju DNK; mjesto njega oni imaju ANK (slovo A dolazi od eng. Alien).

Svaki ANK zapisujemo kao niz međusobno različitih brojeva.

U Primoštenu su jučer, nakon probnog natjecanja, u dvorani za natjecanje pronađeni tragovi dvaju ANK.

Nije nam poznato tko ih je tamo ostavio. Primijetili smo da se sastoje od istih brojeva, ali u različitom poretku, pa smo vam odlučili postaviti sljedeći zadatak.

Podijeli (razreži) prvi ANK na što manje komada i onda dobivene komade presloži i ponovno spoji tako da dobiješ drugi ANK. Na primjer, ovako (3. primjer niže):

Mogli smo u ovom primjeru rezati i na više komada: na primjer, mogao je svaki broj biti zaseban komad.

Ipak, budući da je svako rezanje, a i spajanje komada veoma zahtjevno i skupo, tvoj je zadatak pronaći najmanji mogući broj komada da bi se iz prvog ANK dobio drugi.

Napomene: nije dozvoljeno izvrnuti komad (npr. [12, 55, 7] → [7, 55, 12]). Niz će u nekim test podacima biti jako velik: pripazi na vremensko ograničenje!

ULAZNI PODATCI

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

U drugom retku nalazi se N međusobno različitih prirodnih brojeva koji čine prvi ANK.

U trećem retku nalazi se N međusobno različitih prirodnih brojeva koji čine drugi ANK.

Oba niza sastoje se od istih brojeva, ali u različitom poretku. Ovi su brojevi manji od 500 000.

IZLAZNI PODATCI

U prvi redak ispiši traženi najmanji broj komada M.

U drugi redak ispiši M - 1 brojeva: pozicije rezova u prvom ANK, poredane po veličini od najmanje.

U treći redak ispiši M - 1 brojeva: pozicije spojeva u drugom ANK, poredane po veličini od najmanje.

(Spoj je mjesto gdje smo spojili dva komada. Rez ili spoj na poziciji K nalazi se između K-tog i (K + 1)- og elementa ANK niza.)

PRIMJERI TEST PODATAKA

Ulaz

3
10 20 30
30 20 10

Izlaz

3
1 2
1 2

Ulaz

4
1 4 2 3
2 3 1 4

Izlaz

2
2
2

Ulaz

9
98 12 55 7 4 36 13 30 125
12 55 7 13 30 125 98 4 36

Izlaz

4
1 4 6
3 6 7