SPOJ Brasil

José investe no mercado de ações com uma estratégia de investimento um tanto quanto complexa.

Considere que José possui duas sequências de inteiros P = (P₁, P₂, ..., P_A) e R = (R₁, R₂, ..., R_B), tal que P é uma sequência de inteiros que representa os preços das últimas A negociações de uma determinada ação e R é uma sequência de inteiros distintos utilizada como referência para decidir se José deve ou não investir nas ações em questão.

A partir da sequência P, José gera uma nova sequência M = (M₁, M₂, ..., M_A) , em que M_i é igual à mediana dos valores da subsequência P(1:i) = (P₁, P₂, ..., P_i), para todo i = 1, 2, ..., A. A mediana da subsequência P(1:i) é definida como o k-ésimo valor da subsequência P(1:i) ordenada em ordem crescente, em que k = ⌈i/2⌉. Por exemplo, se temos a sequência de preços P = (5, 3, 2, 1, 4, 2), então:

• M₁ = mediana de P(1:1) = mediana de (5) = primeiro valor de (5) = 5
• M₂ = mediana de P(1:2) = mediana de (5, 3) = primeiro valor de (3, 5) = 3
• M₃ = mediana de P(1:3) = mediana de (5, 3, 2) = segundo valor de (2, 3, 5) = 3
• M₄ = mediana de P(1:4) = mediana de (5, 3, 2, 1) = segundo valor de (1, 2, 3, 5) = 2
• M₅ = mediana de P(1:5) = mediana de (5, 3, 2, 1, 4) = terceiro valor de (1, 2, 3, 4, 5) = 3
• M₆ = mediana de P(1:6) = mediana de (5, 3, 2, 1, 4, 2) = terceiro valor de (1, 2, 2, 3, 4, 5) = 2

Assim, se P = (5, 3, 2, 1, 4, 2), temos que M = (5, 3, 3, 2, 3, 2).

Após determinar a sequência M, José a compara com a sequência de referência R, formada por inteiros distintos e obtida através de informações privilegiadas, que representa a sequência ótima de valores para as medianas dos preços das últimas negociações de uma determinada ação. Assim, se as sequências M e R forem iguais, José pode investir tranquilamente tendo a certeza de que consiguirá obter o maior lucro possível em seu investimento.

Como é muito difícil que as sequências M e R sejam iguais, José considera suficiente que elas sejam ao menos bastante similares para que ele invista nas ações. Assim, para determinar o quanto a sequência M se assemelha da sequência R, José deve calcular a maior subsequência comum de M e R.

Uma subsequência X' de uma sequência de inteiros X é obtida a partir da remoção de zero ou mais inteiros de X, com os elementos de X' aparecendo na mesma ordem em que aparecem em X. Por exemplo, se X = (2, 4, 1, 1, 2, 3), então X' = (2, 1, 1, 3) é uma subsequência de X, enquanto X' = (1, 4) e X' = (2, 1, 5) não são subsequências de X. Assim, as subsequências comuns das duas sequências (5, 3, 3, 2, 4) e (4, 5, 3, 4) são (), (3), (4), (5), (5, 3), (5, 4) e (5, 3, 4), sendo a última a maior delas, com tamanho 3.

José está com dificuldades para determinar se deve ou não investir nas ações e precisa da sua ajuda. Para tanto, dadas as sequências P e R, você deve calcular o tamanho da maior subsequência comum de M e R, em que M é a sequência de medianas calculada da maneira descrita anteriormente.

Entrada

Há vários casos de teste.

Cada caso de teste é descrito em duas linhas. A primeira linha inicia com um inteiro A (1 ≤ A ≤ 100.000) que representa o tamanho da sequência P, seguido de A inteiros que representam a sequência P. A segunda linha inicia com um inteiro B (1 ≤ B ≤ 100.000) que representa o tamanho da sequência R, seguido de B inteiros distintos que representam a sequência R. Todos os inteiros das sequências P e R são maiores ou iguais a 0 e menores ou iguais a 1.000.000.000.

A entrada termina com A=0, que não deve ser processado.

Saída

Para cada caso de teste, imprima uma única linha contendo um único inteiro, o tamanho da maior subsequência comum de M e R.

Exemplos

Entrada:
6 5 3 2 1 4 2
5 5 1 2 7 3
4 1 2 3 4
7 7 6 5 4 3 2 1
3 1 1 1
5 2 4 3 5 6
0

Saída:
3
1
0