3683 - Who's left? Who's right?

Created by Óscar Dávalos Orozco
Added by jicote (2016-06-10)
Limits
Total Time: 45000 MS | Test Time: 8000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

You are given a set S initially containing two integers: 0 and 1000000. You are also given a sequence A of exactly N integer numbers between 1 and 999999. For each number Ai, in the same order they were given, you must perform the following steps:

  1. Find the maximum element x in S which is smaller or equal to Ai
  2. Find the minimum element y in S which is greater than or equal to Ai
  3. Print these pair of numbers x and y
  4. Add Ai to the set S

Notice that step 4 is done after printing the pair of numbers x and y.

Se le ha dado un conjunto S que inicialmente contiene sólo los elementos: 0 y 1000000. También se le dará una secuencia A con exactamente N números enteros entre 1 y 999999. Por cada número Ai, en el mismo orden que serán dados, usted debe ejecutar los siguientes pasos:

  1. Encontrar el máximo elemento x en S que es menor o igual a Ai
  2. Encontrar el mínimo elemento y en S que es mayor o igual a Ai
  3. Imprimir este par de números x e y
  4. Adicionar Ai al conjunto S

Tenga en cuenta que el paso 4 se realiza luego de imprimir el par de números x e y.

;jsessionid=7ED00802CC25A11BD59D57A2D56F98D0

You are given a set S initially containing two integers: 0 and 1000000. You are also given a sequence A of exactly N integer numbers between 1 and 999999. For each number Ai, in the same order they were given, you must perform the following steps:

  1. Find the maximum element x in S which is smaller or equal to Ai
  2. Find the minimum element y in S which is greater than or equal to Ai
  3. Print these pair of numbers x and y
  4. Add Ai to the set S

Notice that step 4 is done after printing the pair of numbers x and y.

Input specification

The first line of input contains an integer N (0 < N < 1000000) representing the number of elements in the sequence A. The following N lines contain one integer each, the element Ai of the sequence.

La primera línea de entrada contiene un número entero N (0 < N < 1000000) que representa la cantidad de elementos en la secuencia A. Las siguientes N líneas contienen un número entero cada una, el elemento Ai de la secuencia.

;jsessionid=7ED00802CC25A11BD59D57A2D56F98D0

The first line of input contains an integer N (0 < N < 1000000) representing the number of elements in the sequence A. The following N lines contain one integer each, the element Ai of the sequence.

Output specification

Output N lines with a pair of space-separated integer numbers per line. In the i-th line, print the maximum element in S which is smaller or equal to Ai and the minimum element in S which is greater than or equal to Ai.

Usted debe imprimir N líneas con un par de números enteros separados por un espacio en cada línea. En la iésima línea, usted debe imprimir el máximo elemento en S que sea menor o igual a Ai y el mínimo elemento en S que sea mayor o igual a Ai.

;jsessionid=7ED00802CC25A11BD59D57A2D56F98D0

The first line of input contains an integer N (0 < N < 1000000) representing the number of elements in the sequence A. The following N lines contain one integer each, the element Ai of the sequence.

Sample input

4
3
1
4
2

Sample output

0 1000000
0 3
3 1000000
1 3

Hint(s)