Problem E
Bílskúrar

Mynd fengin af wikimedia.org

Hannes býr í Brúnalandi. Í Brúnalandi er aðeins ein gata og eru öll húsin öðrum megin við götuna. Hinum megin við götuna eru bílskúrarnir. Hvert hús er með númer og hver bílskúr er einnig með númer. Eigandi hús á þá einnig bílskúrinn með sama númeri.

Eðlilegast væri að húsin væru númeruð í hækkandi röð og að bílskúr hvers húss væri beint á móti húsinu. Brúnaland var hins vegar ekki planað mjög vel og er röð húsanna og bílskúranna í algjöru rugli.

Þegar húseigendur ferðast milli húss og bílskúrs ferðast þeir eftir beinni línu. Þetta getur skapað marga árekstra þegar fólk er að ferðast milli húsa og bílskúra sinna. Hversu mörg pör húseigenda geta mögulega lent í árekstri á leið í bílskúrana sína.

Inntak

Fyrsta línan í inntakinu inniheldur eina heiltölu $n$ ($1 \leq n \leq 2\cdot 10^5$), fjöldi húsa í götunni. Önnur línan inniheldur $n$ heiltölur, sem lýsa í hvaða röð húsin eru. Hver tala á bilinu $1$ upp í $n$ kemur fyrir nákvæmlega einu sinni. Þriðja línan inniheldur $n$ heiltölur, sem lýsa í hvaða röð bílskúrarnir eru. Hver tala á bilinu $1$ upp í $n$ kemur fyrir nákvæmlega einu sinni.

Úttak

Skrifaðu út eina heiltölu, fjölda árekstra sem gætu átt sér stað.

Útskýring á sýnidæmi

Fyrsta sýnidæmið fellur undir hóp 3. Þar má sjá leiðirnar sem húseigendurnir ganga frá húsum að bílskúrum og alla mögulega árekstra sem gætu átt sér stað, merktir með fylltum rauðum hringjum.

Figure 1: Sýnidæmi 1

Stigagjöf

5
1 3 2 5 4
2 1 3 4 5

3

4
1 2 3 4
4 3 2 1

6

7
3 5 2 7 6 4 1
3 5 2 7 6 4 1

0