Perché la mucca ha attraversato la strada II (Oro)#10539
Il Fattore John alleva razze di mucche, che per comodità sono numerate da a . Alcune coppie di razze sono più amichevoli tra loro rispetto ad altre. Questa proprietà può essere determinata semplicemente dai numeri delle razze: le razze e sono amichevoli se |a - b| \le 4, e non amichevoli in caso contrario.
Attraverso la fattoria del Fattore John passa una lunga strada. Su un lato della strada si trova una sequenza di campi — uno per ogni razza. Sul lato opposto della strada si trova anch'esso una sequenza di campi, uno per ogni razza. Per aiutare le mucche ad attraversare la strada in sicurezza, il Fattore John vuole costruire dei passaggi pedonali che colleghino i campi sui lati opposti della strada. Un passaggio può essere costruito solo tra due campi i cui numeri di razza sono amichevoli.
Dato l'ordine di disposizione degli campi su ciascun lato della strada, aiuta il Fattore John a determinare il numero massimo di passaggi pedonali che può costruire in modo che nessuno due passaggi si intersechino.
La prima riga contiene il numero n~(1 \le n \le 1000).
Le successive righe descrivono l'ordine dei campi su un lato della strada in base ai numeri delle razze. Ogni numero di razza è un numero intero compreso tra e .
Le successive righe descrivono l'ordine dei campi sull'altro lato della strada, anch'esso in base ai numeri delle razze. Ogni numero di razza compare esattamente una volta in ciascuno dei due ordini.
Stampa il numero massimo di «passaggi amichevoli» che non si intersecano che il Fattore John può costruire attraverso la strada.
Esempio 1