Problema A - Visit Onitugal

A República de Onitugal viveu sempre muito do turismo. Como o turismo foi muito limitado recentemente, os onitugueses querem tornar Onitugal num destino mais apelativo. A cordilheira dos Onimalaias, que consiste numa fila de N montanhas cada uma com uma certa altura A_i, é dos locais mais bonitos do país, pelo que o governo está a avaliar se deve investir em infraestrutura nesta região, tendo dois planos possíveis.

Parte I

Um dos planos do governo consiste em construir pontes entre as montanhas para melhor circulação. É possível construir uma ponte entre duas montanhas se elas tiveram a mesma altura. O ministério do turismo, que carece informáticos, pediu-te para determinar quantas pontes é possível construir.

Exemplo

Se tivermos N = 8 montanhas de alturas (4, 5, 9, 4, 3, 1, 3, 5) é possível construir 3 pontes, entre as montanhas (1, 4), (2, 8) e (5, 7).

A seguinte figura ilustra este caso:

Se tivermos N = 6 montanhas de alturas (1, 2, 4, 2, 2, 3) é possível construir 3 pontes, entre as montanhas (2, 4), (2, 5) e (4, 5).

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Parte II

O outro plano do governo consiste em construir um passeio paralelo à cordilheira, no qual é possível tirar lindas fotos deste fenómeno da natureza. Uma foto da cordilheira é considerada bonita se tiver um número ímpar de montanhas e se a montanha no centro for a estritamente maior. A tua tarefa é determinar qual o maior número de montanhas que uma foto bonita pode ter e quantas fotos bonitas é possível tirar.

Exemplo

Se tivermos N = 8 montanhas de alturas (2, 5, 9, 2, 3, 1, 3, 5) é possível tirar 11 fotos bonitas: 1 a 5, 2 a 4, 4 a 6 e as 8 fotos com apenas uma montanha, sendo o máximo de montanhas de uma foto bonita 5 montanhas

A seguinte figura ilustra este caso:

Se tivermos N = 6 montanhas de alturas (3, 2, 4, 2, 2, 1) é possível tirar 8 fotos bonitas: 1 a 5, 2 a 4 e as 6 fotos com apenas uma montanha, sendo o máximo de montanhas de uma foto bonita 5 montanhas

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Sumário de subtarefas

Os casos de teste do problema estão organizados em 4 grupos com restrições adicionais diferentes:

Input

Nota: O formato de input é o mesmo para as duas partes.

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.

Segue-se uma linha com um inteiro N, representando o número de montanhas.

Segue-se uma linha com N inteiros separados por espaços, as alturas de cada montanha.

Output

Parte I

O output deve conter uma só linha com o número de pontes que se pode construir.

Parte II

O output deve conter uma só linha com dois inteiros separados por espaços, primeiro o maior número de montanhas que uma foto bonita pode ter e depoos o número de fotos bonitas que é possível tirar.

Input do Exemplo 1

1
8
4 5 9 4 3 1 3 5

Output do Exemplo 1

3

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.

Input do Exemplo 2

1
6
1 2 4 2 2 3

Output do Exemplo 2

3

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.

Input do Exemplo 3

2
8
2 5 9 2 3 1 3 5

Output do Exemplo 3

5 11

Explicação do Exemplo 3

Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.

Input do Exemplo 4

2
6
3 2 4 2 2 1

Output do Exemplo 4

5 8

Explicação do Exemplo 4

Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.