28a Olimpíada Brasileira de Informática
Submeta sua solução

Construtora

Em uma rua existem N prédios adjacentes, o i-ésimo entre eles (da esquerda para a direita) possui ai andares. Uma construtora acabou de comprar todos os prédios da rua, e fará uma obra para que eles tenham a mesma altura (quantidade de andares), porém, para realizar esta obra ela deve seguir as regras definidas pela Sociedade Brasileira de Construção (SBC). Segundo as regras da SBC, cada fase da obra só pode aumentar em uma unidade a quantidade de andares de prédios consecutivos que já possuam uma mesma quantidade de andares. Sendo mais específico, para cada fase:
  • A construtora deve definir um índice inicial L
  • A construtora deve definir um índice final R
  • Todos os prédios entre L e R (incluindo L e R) devem possuir a mesma quantidade de andares, digamos a
  • Ao final desta fase da obra, todos os prédios entre L e R (incluindo L e R) vão possuir a + 1 andares
Por exemplo, suponha que N seja igual a 8, e que as alturas iniciais sejam: a1=5, a2=4, a3=4, a4=4, a5=5, a6=4, a7=4 e a8=7, perceba que:
  • A construtora não pode definir L=2 e R=7 para a primeira fase, pois nem todas as quantidades de andares nesse intervalo de prédios são iguais
  • A construtora não pode definir L=1 e R=5 para a primeira fase, pois nem todas as quantidades de andares nesse intervalo de prédios são iguais
  • A construtora pode definir L=8 e R=8 para a primeira fase, e a quantidade de andares final seria: a1=5, a2=4, a3=4, a4=4, a5=5, a6=4, a7=4 e a8=8
  • A construtora pode definir L=2 e R=4 para a primeira fase, e a quantidade de andares final seria: a1=5, a2=5, a3=5, a4=5, a5=5, a6=4, a7=4 e a8=7
Para cada fase da obra, a construtora deve pagar impostos para a prefeitura, portanto, ela deseja completar a tarefa usando a menor quantidade possível de fases. No exemplo mostrado anteriormente a menor quantidade de fases é 4, você consegue enxergar como? Dadas a quantidade inicial de andares de cada um dos N prédios, sua tarefa é determinar a quantidade mínima de fases para completar a obra.

Entrada

A primeira linha da entrada contém um único inteiro N, o número de prédios da rua. A segunda linha contém N inteiros, o i-ésimo entre esses inteiros é ai, a quantidade de andares do i-ésimo prédio.

Saída

A saída deve conter um único número inteiro, a menor quantidade de fases necessárias para a construtora completar a obra, ou seja, deixar todos os prédios com a mesma altura.

Restrições

  • 2 ≤ N ≤ 100.
  • 1 ≤ ai ≤ 100.

Informações sobre a pontuação

A tarefa vale 100 pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima.
  • Subtarefa 1 (0 pontos): Esta subtarefa é composta apenas pelos exemplos mostrados abaixo. Ela não vale pontos, serve apenas para que você verifique se o seu programa imprime o resultado correto para os exemplos.
  • Subtarefa 2 (17 pontos): ai = aj para todo 1 ≤ i,j ≤ N-1, ou seja, todos os N-1 primeiros prédios possuem a mesma altura inicial.
  • Subtarefa 3 (18 pontos): 1 ≤ ai ≤ 2.
  • Subtarefa 4 (19 pontos): 1 ≤ ai ≤ 3.
  • Subtarefa 5 (20 pontos): ai > aj para todo 1 ≤ i < j ≤ N, ou seja, as alturas iniciais dos prédios são decrescentes da esquerda para a direita.
  • Subtarefa 6 (26 pontos): Sem restrições adicionais.

Exemplos

Entrada
4
3 1 1 2
Saída
2
	

 

Entrada
8
5 4 4 4 5 4 4 7
Saída
4
	

 

Entrada
3
100 100 100
Saída
0
	

 

PJ P1 P2 PS
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação