Informática – Nível Avançado – Semana 9

por

Roda-roda

Após o misterioso desaparecimento de Ashish, seus dois discípulos favoritos Ishika e Hriday foram deixados cada um com metade de uma mensagem secreta. Essas mensagens podem ser representadas por uma permutação de tamanho $$n$$. Vamos chamar elas de $$a$$ e $$b$$.

Note que uma permutação de $$n$$ elementos é uma sequência de números $$a_1$$, $$a_2$$, …, $$a_n$$, onde todo número de $$1$$ até $$n$$ aparece exatamente uma vez.

A mensagem secreta pode ser decodificada por um rearranjo das sequências $$a$$ e $$b$$, tal que o número de pares que combinam seja máximo. Um par de elementos $$a_i$$ e $$b_i$$ combinam se:

  • $$i=j$$, isso é, eles estão no mesmo índice.
  • $$a_i=b_j$$

Seus dois discípulos podem realizar a seguinte operação quantas vezes quiserem:

  • escolher um número $$k$$ e rotacionar a permutação $$k$$ vezes para esquerda ou $$k$$ vezes para a direita.

Uma simples rotação para a esquerda em uma permutação $$c$$ é uma operação que transforma $$c_1 := c_2$$, $$c_2 := c_3$$, …, $$c_n := c_1$$ simultaneamente.

Ajude Ishika and Hriday a encontrar o número máximo de pares que combinam após performar a operação qualquer (possivelmente zero) número de vezes.

Entrada

A primeira linha da entrada contêm um inteiro $$n$$ $$(1 \leq n \leq 2 \cdot 10^5)$$ representando o tamanho das permutações.

A segunda linha contém $$n$$ inteiro $$a_1$$, $$a_2$$, …, $$a_n$$ $$(1 \leq a_i \leq n)$$ representando os elementos da primeira permutação.

A terceira linha contém $$n$$ inteiro $$b_1$$, $$b_2$$, …, $$b_n$$ $$(1 \leq b_i \leq n)$$ representando os elementos da segunda permutação.

Saída

Imprima o número máximo de pares que combinam após realizar todas as operações.

Exemplos:

Entrada Saída
5
1 2 3 4 5
2 3 4 5 1
5
5
5 4 3 2 1
1 2 3 4 5
1
4
1 3 2 4
4 2 3 1
2