Perché la mucca ha attraversato la strada II (Platino)#10542
Il fattore John continua a riflettere sul problema dell'attraversamento della strada da parte delle mucche che attraversa la sua fattoria, presentato nel problema precedente. Si rende conto che l'interazione tra alcune coppie di razze è del tutto ammissibile, se tali razze sono amichevoli. Questa proprietà può essere semplicemente determinata dagli identificatori delle razze: le razze e sono amichevoli se |a - b| \le 4, e non amichevoli in caso contrario. Alle mucche è permesso entrare nei campi destinati ad altre razze, se tali razze sono amichevoli.
Dato l'ordine di disposizione di campi su entrambi i lati della strada nella fattoria del Fattore John (su ciascun lato si trova esattamente un campo per ogni razza), aiutate il Fattore John a determinare il numero massimo di attraversamenti pedonali che può costruire attraverso la strada in modo che nessuna coppia di attraversamenti si intersechi e ogni attraversamento colleghi campi destinati a razze amichevoli. Ogni campo può essere collegato da al massimo un attraversamento, quindi nessuna coppia di attraversamenti deve avere un'estremità in comune.
Nella prima riga è contenuto il numero n~(1 \le n \le 10^5). Le successive righe descrivono l'ordine di disposizione dei campi su un lato della strada in base agli identificatori delle razze. Ogni identificatore di razza è un numero intero compreso tra e .
Le successive righe descrivono l'ordine di disposizione dei campi sull'altro lato della strada, anch'esso in base agli identificatori delle razze. Ogni identificatore di razza compare esattamente una volta in ciascuno dei due ordini.
Stampate il numero massimo di "attraversamenti amichevoli" non intersecanti che il Fattore John può costruire attraverso la strada.
Esempio 1