Perché la mucca ha attraversato la strada III (Platino)#10543
Il Fattore John continua a esplorare il problema dell'attraversamento della strada da parte delle mucche che attraversa la sua fattoria, presentato nei due problemi precedenti. Ora si rende conto che il criterio di amicizia è più complesso di prima: le razze e sono considerate amichevoli se |a - b| \le k, e non amichevoli in caso contrario.
Dato l'ordine di disposizione dei campi su entrambi i lati della strada nella fattoria del Fattore John, determina il numero di coppie di razze non amichevoli che si incrociano, dove una coppia che si incrocia è definita nello stesso modo dei problemi precedenti.
Nella prima riga sono contenuti due numeri interi n~(1 \le n \le 10^5) e k~(0 \le k < n).
Le successive righe descrivono l'ordine di disposizione dei campi su un lato della strada tramite identificatori di razza. 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 tramite identificatori di razza. Ogni identificatore di razza compare esattamente una volta in ciascuno dei due ordini.
Stampa il numero di coppie di razze non amichevoli che si incrociano.
In questo esempio, le razze e formano una coppia non amichevole che si incrocia, così come le razze e .
Esempio 1