O arquivo de entrada consiste de vários conjuntos de dados. Cada conjunto de dados contém duas linhas: a primeira linha contém o número N de elementos do array (2 ≤ N ≤ 1000) e a segunda linha contém os elementos (inteiros) que serão ordenados. Um conjunto com N = 0 indica o fim do arquivo, e não deve ser processado.

Entrada exemplo:
6
6 5 4 3 2 1
6
1 2 3 4 5 6
7
4 3 1 2 6 5 7
0

       O arquivo de saída deve mostrar o número do conjunto e, após cada chamada ao procedimento de partição, imprimir o pivô escolhido e a configuração atual do array. Uma linha em branco deve ser impressa após cada conjunto.

Saída exemplo correspondente à entrada acima:
Conjunto #1
4: 3 1 2 4 6 5
2: 1 2 3 4 6 5
6: 1 2 3 4 5 6

Conjunto #2
3: 1 2 3 4 5 6
1: 1 2 3 4 5 6
5: 1 2 3 4 5 6

Conjunto #3
4: 2 3 1 4 6 5 7
2: 1 2 3 4 6 5 7
6: 1 2 3 4 5 6 7

Obs.:

• O pivô escolhido sempre será a mediana entre o primeiro elemento, o último e o central;
• Ao calcular a mediana, se houverem números iguais, dê preferência ao primeiro elemento, e em seguida ao último;
• Elementos idênticos ao pivô devem ficar na partição à esquerda;
• O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.

       O arquivo de entrada consiste de vários conjuntos de dados. Cada conjunto de dados contém duas linhas: a primeira linha contém o número N de elementos do array (1 ≤ N ≤ 1000) e a segunda linha contém os elementos (inteiros) que serão ordenados. Um conjunto com N = 0 indica o fim do arquivo, e não deve ser processado.

Entrada exemplo:
4
8 4 3 1
3
1 2 3
5
1 3 2 5 4
0

       O arquivo de saída deve mostrar o número do conjunto e, após cada chamada ao procedimento mergesort, imprimir que intervalo do array que foi ordenado e a configuração atual do array. Uma linha em branco deve ser impressa após cada conjunto.

       O intervalo deve ser impresso na forma A-B, em que A indica o índice inicial e B o índice final. Os índices estão entre 1 e N.

Saída exemplo correspondente à entrada acima:
Conjunto #1
1-1: 8 4 3 1
2-2: 8 4 3 1
1-2: 4 8 3 1
3-3: 4 8 3 1
4-4: 4 8 3 1
3-4: 4 8 1 3
1-4: 1 3 4 8

Conjunto #2
1-1: 1 2 3
2-2: 1 2 3
1-2: 1 2 3
3-3: 1 2 3
1-3: 1 2 3

Conjunto #3
1-1: 1 3 2 5 4
2-2: 1 3 2 5 4
1-2: 1 3 2 5 4
3-3: 1 3 2 5 4
1-3: 1 2 3 5 4
4-4: 1 2 3 5 4
5-5: 1 2 3 5 4
4-5: 1 2 3 4 5
1-5: 1 2 3 4 5

Obs.:

• Caso seja encontrado um array de tamanho ímpar, o elemento central deve ficar na partição à esquerda;
• O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.