URI Online Judge | 0

Amarelinha da Mofhia

Por Pedro Diogo Machado, UFU BR Brazil

Timelimit: 1

O jogo da “Amarelinha da Mofhia” é um jogo que está ficando muito popular nos campos da Nlogônia.

Mofhia é uma menina muito feliz e adora brincar com seu amigo Sarcos nas horas vagas, o jogo preferido deles era a amarelinha.

De uns tempos pra cá, a menina Mofhia ficou muito boa no jogo da amarelinha e ganhava sempre do seu amigo Sarcos e, como Sarcos odeia perder, ele resolveu desafiar Mofhia criando um novo jogo parecido com a amarelinha que acabou ficando conhecido como Amarelinha da Mofhia.

As regras são as seguintes:

  1. Sarcos escolhe um número representando a quantidade de quadradinhos que ele vai desenhar.

  2. Ele, depois, desenha todos os quadradinhos um ao lado do outro.

  3. Como o jogo pode ter muitos quadradinhos e a Mofhia não ia aguentar ficar pulando o dia todo, ele escolhe alguns quadradinhos para serem pontos de descanso, onde a Mofhia pode parar pra tomar um ar durante o jogo.

  4. Esse pontos de descanso vão ser marcados com o número zero. O primeiro quadradinho vai ser sempre um ponto de descanso, para que a Mofhia possa se preparar para começar a partida, e o último quadradinho também, para que ela possa ter um tempo pra recuperar o fôlego e comemorar depois do fim da partida.

  5. Sarcos, então, vai escolher um número para cada quadrinho restante, que vai ser a pontuação que a Mofhia vai ganhar se ela pisar naquele quadradinho.

  6. Quando a Mofhia está em um quadradinho de um tipo, ela só pode pular para quadradinhos de um tipo diferente. Isto é, se ela está num ponto de descanso ela tem que pular para um quadradinho pontuado, e se ela está em um quadradinho pontuado ela tem que ir para um ponto de descanso no seu próximo pulo.

  7. Mofhia nunca pode pular duas vezes no mesmo quadradinho, nem pular para um quadradinho que está atrás da sua posição no momento.

  8. Mofhia tem que fazer o maior número de pontos possíveis no jogo para ganhar.

Enquanto Sarcos estava ocupando criando as regras do jogo, Mofhia estava praticando fitdance para ganhar força nas pernas. Por isso, Mofhia consegue pular para qualquer quadradinho que ela queira sem errar, não importa quão longe ele esteja.

Mofhia é uma menina muito esperta e poderia resolver esse problema sozinha, mas como ela estava ocupada treinando suas coreografias especiais, ela pediu você pra fazer um programa que calcula a maior pontuação possível em uma partida de Amarelinha da Mofhia.

Entrada

A primeira linha possui um inteiro N representando a quantidade de quadradinhos

A segunda linha da entrada possui inteiros \(x_i\) representando o número de cada quadradinho

1 \(\leq\) \(\leq\) \(10^5\)

1 \(\leq\) \(x_i\) \(\leq\) \(10^2\)

Os zeros representam os pontos de descanso.

É garantido que o primeiro e o último quadradinhos são pontos de descanso.

Saída

Apenas um inteiro representando a resposta.

Exemplos de Entrada Exemplos de Saída

8

0 2 5 1 9 0 3 0

12

7

0 2 0 5 0 3 0

10

10

0 2 5 3 7 1 9 15 3 0

15