URI Online Judge | 3050

Distância Entre Amigos

Por BR Brazil

Timelimit: 1

Ao longo da rua existem N prédios de largura igual, mas com número de andares diferentes. Quase toda a turma do colégio mora em algum apartamento desses prédios e eles resolveram definir a distância entre dois apartamentos quaisquer da rua para saber, ao final, qual par de colegas da turma mora mais longe um do outro.

Funciona assim: para um colega A visitar um colega B, que mora num prédio diferente, ele deve descer a andares até o térreo do seu prédio; depois andar para a esquerda ou direita, dependendo do lado para o qual seu colega mora, por p prédios; depois subir b andares até o apartamento do colega B. A distância entre A e B, então, será a+p+b. A figura mostra um exemplo, para N = 14, onde estão marcados dois andares de prédios diferentes para os quais a distância é 12. Dado um número de andares de cada prédio ao longo da rua, seu programa deve computar a distância máxima possível entre dois apartamentos quaisquer na rua.

Entrada

A primeira linha da entrada contém um inteiro N representando o número de prédios na rua. A segunda linha contém N inteiros Ai , 1 ≤ i ≤ N, representando o número de andares de cada prédio, sem contar o térreo. Quer dizer, por exemplo, se Ai = 19, então quem mora no último andar precisa descer 19 andares até o térreo. Veja a figura, que corresponde ao primeiro exemplo de entrada abaixo.

Saída

Seu programa deve imprimir uma linha contendo um número inteiro representando a distância máxima possível entre dois apartamentos na rua.

Restrições

2 ≤ N ≤ 200000(2 × 105 );

1 ≤ Ai ≤ 109 para todo 1 ≤ i ≤ N.

Informações sobre a pontuação

• Em um conjunto de casos de teste somando 25 pontos, N ≤ 104 e Ai ≤ 104 

• Em um conjunto de casos de teste somando 25 pontos, Ai ≤ 100

• Em um conjunto de casos de teste somando 50 pontos, nenhuma restrição adicional

Exemplos de Entrada Exemplos de Saída

14

2 3 1 6 4 3 7 5 6 4 5 3 1 1

18

6

1 1 4 3 1 2

9

2

1 1

3