Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

ACOES2MG - Investindo no mercado de ações 2

no tags 

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 = (P1, P2, ..., PA) e R = (R1, R2, ..., RB), 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 = (M1, M2, ..., MA) , em que Mi é igual à mediana dos valores da subsequência P(1:i) = (P1, P2, ..., Pi), 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:

  • M1 = mediana de P(1:1) = mediana de (5) = primeiro valor de (5) = 5
  • M2 = mediana de P(1:2) = mediana de (5, 3) = primeiro valor de (3, 5) = 3
  • M3 = mediana de P(1:3) = mediana de (5, 3, 2) = segundo valor de (2, 3, 5) = 3
  • M4 = mediana de P(1:4) = mediana de (5, 3, 2, 1) = segundo valor de (1, 2, 3, 5) = 2
  • M5 = mediana de P(1:5) = mediana de (5, 3, 2, 1, 4) = terceiro valor de (1, 2, 3, 4, 5) = 3
  • M6 = 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

Added by:Wanderley Guimarăes
Date:2012-06-21
Time limit:2.207s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Maratona Mineira 2012