Alicia i Beatriz przygotowują sztuczkę magiczną na pokaz talentów IOI. Sztuczka przebiega następująco:

• Wolontariusz wybiera permutację $P$ o długości $N$ i kładzie na stole $N$ kart. Karty są ponumerowane od $0$ do $N - 1$, a karta $i$ pokazuje wartość $P[i]$.
• Alicia wchodzi do pokoju, obserwuje karty i wybiera $K$ z nich, które odwraca rewersem do góry, ukrywając ich wartości.
• Następnie do pokoju wchodzi Beatriz, widzi obecny układ kart (w tym to, które z nich są odwrócone) i magicznie odgaduje wartości wszystkich $K$ ukrytych kart!

Twoim zadaniem jest opracowanie i zaimplementowanie strategii dla Alicii i Beatriz. Im bardziej imponująca sztuczka, tym lepszy wynik: celem jest zmaksymalizowanie $K$, czyli liczby ukrytych kart, które Beatriz potrafi poprawnie odgadnąć.

Szczegóły implementacji

Pierwsza procedura, którą musisz zaimplementować:

std::vector<int> Alicia(std::vector<int> P)

• $P$: tablica o długości $N$, reprezentująca wybraną permutację.

Ta procedura powinna zwrócić tablicę $Q$ o długości $N$, reprezentującą odwrócenia kart wykonane przez Alicię. Dla każdego indeksu $i$ ($0 \le i \le N - 1$), wartości w $Q$ muszą być ustawione następująco:

• $Q[i] = -1$, jeśli Alicia odwraca kartę $i$, oraz
• $Q[i] = P[i]$ w przeciwnym przypadku.

Druga procedura, którą musisz zaimplementować:

std::vector<int> Beatriz(std::vector<int> Q)

• $Q$: tablica o długości $N$, zwrócona przez Alicię. Ta tablica określa konfigurację kart, gdy wchodzi Beatriz.

Ta procedura powinna zwrócić tablicę $B$ o długości $N$, reprezentującą oryginalną permutację $P$, to znaczy dla każdego $i$ ($0 \le i \le N - 1$) powinno zachodzić $B[i] = P[i]$.

W każdym przypadku testowym obie procedury są wywoływane dokładnie raz, w następujący sposób:

• Podczas pierwszego uruchomienia programu:
  • Alicia jest wywoływana z oryginalną permutacją $P$.
  • Dla tablicy $Q$ zwróconej przez Alicię:
    • Jeśli tablica nie jest zgodna z opisanymi powyżej ograniczeniami, otrzymasz werdykt Output isn't correct.
    • W przeciwnym razie tablica $Q$ jest przechowywana przez system oceniający.
• Podczas drugiego uruchomienia programu:
  • Beatriz jest wywoływana z tablicą $Q$.

Ograniczenia

• $N = 256$
• $1 \le P[i] \le N$ dla każdego $i$ takiego, że $0 \le i < N$.
• Wszystkie wartości w $P$ są różne.

Podzadania

Niech $M$ będzie minimalną wartością $K$, dla której Twoje rozwiązanie skutecznie wykonuje sztuczkę we wszystkich przypadkach testowych.

• Jeśli $M = 0$ lub Twoje rozwiązanie nie potrafi poprawnie odtworzyć permutacji $P$ w jakimkolwiek przypadku testowym, otrzymujesz 0 punktów.
• W przeciwnym razie Twój wynik wynosi: $$\min(20 + 5 \cdot M, 100)$$

W szczególności, pełny wynik uzyskuje się dla $M = 16$.

Przykład

Rozważmy scenariusz, w którym $N = 6$ i $P = [2, 4, 3, 1, 5, 6]$. Procedura Alicia jest wywoływana jako:

Alicia([2, 4, 3, 1, 5, 6])

Załóżmy, że Alicia stosuje następującą strategię: odwraca każdą kartę $i$ taką, że $P[i] = i + 1$. W tym przypadku warunek jest spełniony dla $i = 2, 4$ oraz $5$. W związku z tym procedura zwraca tablicę $[2, 4, -1, 1, -1, -1]$.

Teraz procedura Beatriz jest wywoływana jako:

Beatriz([2, 4, -1, 1, -1, -1])

Znając strategię Alicii, znajduje ona i zwraca oryginalną tablicę $P = [2, 4, 3, 1, 5, 6]$.

W tym przypadku $K = 3$, ponieważ odwrócono trzy karty. Jednakże, w przypadku przesłania, ta strategia otrzymałaby 0 punktów, ponieważ istnieją permutacje, w których żaden indeks $i$ nie spełnia warunku $P[i] = i + 1$.

Zauważ, że ten przykład nie spełnia ograniczenia $N = 256$ i dlatego nie będzie używany podczas oceniania. Dołączony do zadania plik zawiera przykładowe wejście dla sprawdzaczki z $N = 256$. Ta sama permutacja $P$ jest używana w Podzadaniu 0 podczas ewaluacji.

Przykładowa sprawdzaczka

Wejście:

N
P[0] P[1] ... P[N-1]

Wyjście:

S
Q[0] Q[1] ... Q[S-1]
T
B[0] B[1] ... B[T-1]

Gdzie:

• $S$ to długość tablicy $Q$ zwróconej przez Alicię.
• $T$ to długość tablicy $B$ zwróconej przez Beatriz.

Zauważ, że chociaż $N = 256$ obowiązuje dla wszystkich przypadków testowych w tym zadaniu, możesz użyć przykładowej sprawdzaczki z dowolną wartością $N$.