Conexión simultánea


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C++

Durante la Olimpiada de Informática de Centroamérica y el Caribe (OICC) los participantes utilizarán la plataforma DMOJ. El sistema registra las conexiones y desconexiones de los usuarios a lo largo de un concurso.

El concurso está dividido en n momentos consecutivos. Para cada momento, se conoce el número total de participantes que se conectaron a la plataforma o se desconectaron de ella.

A partir de esta información, determina la menor y la mayor cantidad posible de participantes que pudieron estar conectados simultáneamente a la plataforma en algún intervalo entre dos momentos consecutivos.

Se garantiza que al inicio y al final del concurso no había ningún participante conectado y que ningún participante se conectó y desconectó en el mismo momento.

Entrada

La primera línea contiene un entero n (2 \le n \le 10^5) - el número de momentos registrados.

La segunda línea contiene n enteros a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) - el número total de participantes que se conectaron o desconectaron de la plataforma en cada momento.

Salida

Imprime dos enteros - la menor y la mayor cantidad posible de participantes que pudieron estar conectados simultáneamente a la plataforma durante el concurso.

Se garantiza que existe al menos una distribución de conexiones y desconexiones que cumple las condiciones descritas.

Subtareas

Esta tarea está compuesta por 3 subtareas.

La puntuación de cada subtarea se determina de la siguiente manera:

  • Se otorgará el 100\% de los puntos si ambos valores son correctos en todos los casos de prueba de la subtarea.
  • Se otorgará el 50\% de los puntos si, en todos los casos de prueba de la subtarea, al menos uno de los dos valores es correcto.
  • Se otorgarán 0 puntos en caso contrario.

Para obtener el 50\% de los puntos, la salida debe contener obligatoriamente los dos enteros en cada caso de prueba.

Subtarea Puntos Restricciones adicionales Dependencias
1 14 1 \le n \le 10, 1 \le a_i \le 10 -
2 28 1 \le n \le 100, 1 \le a_i \le 10 1
3 58 Sin restricciones adicionales 1-2

Ejemplos

Entrada 1
4
5 3 4 6
Salida 1
6 8

Para conseguir la menor cantidad máxima de participantes conectados simultáneamente, la plataforma pudo tener 5, 2 y 6 participantes conectados entre momentos consecutivos. En el primer momento se conectaron 5 participantes, en el segundo momento se desconectaron 3 participantes quedando 5-3=2 conectados, en el tercer momento se conectaron 4 participantes dejando 2+4=6 conectados que se desconectaron en el cuarto momento.

Para conseguir la mayor cantidad máxima, estas cantidades pudieron ser 5, 8 y 6. En el primer momento se conectaron 5 participantes, en el segundo momento se conectaron 3 participantes dejando 5+3=8 conectados, en el tercer momento se desconectaron 3 participantes y se conectó 1 dejando 8-3+1 conectados que se desconectaron en el cuarto momento.


Comments

There are no comments at the moment.