Tiket

시간 제한1초메모리 제한1024 MB

요약

경주 결과에서 a가 b보다 앞서고, 세 개의 티켓이 모두 a와 b의 순서를 같게 예측한 쌍 (a,b)의 수를 센다.

난이도: 보통10점 중 6점
유형: 정렬, 조합론, 누적 합
정답자: 아직 제출이 없습니다

문제

Osim ako živite ispod kamena, zasigurno ste upoznati s činjenicom da će Josip, Marin i Paula predstavljati hrvatsku na finalu studentskog ICPC natjecanja ~~2020.~~ 2021. godine u Rusiji. Zanimljivo je da su im pripreme za natjecanje pomalo nekonvencionalne. Naime, umjesto da rješavaju stara finala, oni uporno smišljaju nove, vlastite zadatke i sudjeluju u organizaciji srednjoškolskih natjecanja. Između ostalog, članovi su znanstvenog povjerenstva i ovogodišnjih Izbornih Priprema.

Vidjevši rezultate prvog dana, odlučili su u potpunosti promijeniti skup zadataka (engl. problemset) prvotno namijenjen drugom danu. Radili su na zadacima cijeli dan i cijelu noć te konačno završili s poslom oko četiri sata ujutro. Zaključili su da im se ne isplati spavati, te su početak natjecanja odlučili zajedno pričekati u lokalnom lokalu gdje za okruglim stolom mogu pijuckati viski s coca-colom.

Marin: Gledajte, u ovom lokalu nalazi se kladomat. Hoćemo li zaigrati jedan tiket?

Josip: Nitko normalan nije ni budan nedjeljom u 4:20 ujutro, a kamoli da se igra neka profesionalna sportska liga.

Paula: Ne znam o čemu pričate, ja samo vidim neke peseke koji trče u krug.

I tako su se naši finalisti odlučili okladiti na utrku pasa. U utrci sudjeluje $N$ pasa označenih prirodnim brojevima od $1$ do $N$ . Svaki od naših finalista kladio se na točan poredak pasa, odnosno na tiketu im piše neka permutacija brojeva od $1$ do $N$ za koju smatraju da će odgovarati konačnom poretku pasa.

Priprema, pozor, sad!

Finalisti su grčevito držali tikete sve dok i zadnji pas nije ušao u cilj. Potom se na displeju pojavila permutacija brojeva od $1$ do $N$ koja odgovara konačnom poretku. Više sreće drugi put. . .

Marin: Dajte da vidim vaše tikete, zanima me broj parova pasa za koje smo svo troje pogodili ili svoje troje pogriješili relativan poredak.

Josip: Hm, zvuči kao dobar zadatak, možda bolje da stavimo to nego da ponovimo onaj sa xorovima.

Paula: Taman stignemo, ali ovaj puta ja radim primjere!

Sve vam je jasno, odredite broj parova pasa $(a, b)$ takvih da je u konačnom poretku pas $a$ stigao u cilj prije psa $b$ , te se na svakom tiketu pas $a$ nalazi prije psa $b$ ili se na svakom tiketu pas $b$ nalazi prije psa $a$ .

입력

U prvom je retku prirodan broj $N$ , broj pasa.

U drugom se retku nalazi permutacija brojeva od $1$ do $N$ koja predstavlja konačan poredak pasa na utrci (od prvog prema posljednjem).

U trećem se retku nalazi permutacija brojeva od $1$ do $N$ koja predstavlja Josipovu okladu (od prvog psa prema posljednjem).

U četvrtom se retku nalazi permutacija brojeva od $1$ do $N$ koja predstavlja Marinovu okladu (od prvog psa prema posljednjem).

U petom se retku nalazi permutacija brojeva od $1$ do $N$ koja predstavlja Paulinu okladu (od prvog psa prema posljednjem).

출력

U jedini redak ispišite traženi broj parova pasa iz teksta zadatka.

힌트

Pojašnjenje trećeg probnog primjera: Svo troje su ispravno pogodili da će pas $3$ stići u cilj prije psa $5$ , te da će pas $4$ stići u cilj prije psa $5$ . Također, svo troje su pogrešno procijenili da će pas $4$ stići u cilj prije psa $3$ .

예제3

예제 1
입력
```
3
2 3 1
1 2 3
1 2 3
2 3 1
```
예상 출력
```
1
```
예제 2
입력
```
4
3 1 2 4
4 3 2 1
1 2 3 4
1 2 4 3
```
예상 출력
```
0
```

예제 3

입력

예상 출력