3. Mínimos e máximos
Problema

Dada uma sequência de valores inteiros, pretende-se calcular a soma dos valores mínimos e máximos das subsequências consecutivas com um dado comprimento.

Se a sequência, constituída por 6 elementos, for a seguinte:

    1 2 3 4 5 6

as subsequências de comprimento 2 consecutivas serão:

    1 2
    3 4
    5 6

A primeira subsequência começa na 1ª posição da sequência, a segunda subsequência começa na 3ª posição (a posição a seguir à do último elemento da primeira subsequência), a terceira subsequência começa na 5ª posição, e assim sucessivamente.

A soma dos valores mínimos destas subsequências é 9 e a soma dos valores máximos é 12.
Tarefa

Faça um programa, em C, que leia uma sequência de valores inteiros do standard input (teclado), seguida de uma sequência de pedidos de cálculo da soma dos valores mínimos ou máximos das subsequências, e que escreva no standard output (consola) as somas calculadas.

Cada pedido indica se se pretende a soma dos mínimos ou dos máximos e o comprimento a considerar para as subsequências.

Se a sequência não for decomponível num número inteiro de subsequências com o comprimento indicado, a última subsequência conterá menos valores que as restantes subsequências, incluindo só os valores que não pertencem a nenhuma outra subsequência.

Entrada (Input)

A primeira linha da entrada do programa contém o número N de elementos da sequência. Seguem-se N linhas, contendo os elementos vi da sequência, um por linha, pela ordem em que aparecem na sequência.

As linhas seguintes, em número indeterminado, conterão, cada uma, o carácter m ou o carácter M, seguido de um espaço e de um inteiro L, que indica o comprimento das subsequências.

Pode considerar que a entrada do programa observa todas as restrições do enunciado.
Limites

1 ≤ N ≤ 10000 	  	Número de elementos da sequência
-231 ≤ vi < 231, 1 ≤ i ≤ N 		Elementos da sequência
1 ≤ L ≤ N 		Comprimento das subsequências
Saída (Output)

Para cada pedido de cálculo da soma dos valores mínimos ou máximos lido, o programa deverá escrever, no standard output, uma linha da forma:

    + min <valor>

onde <valor> é a soma dos mínimos das subsequências, se o carácter do pedido for o m; ou da forma:

    + max <valor>

onde <valor> é a soma dos máximos das subsequências, se o carácter do pedido for o M.

A ordem do output produzido deverá corresponder à ordem de leitura dos pedidos.
Exemplo 1
Entrada

6
1
2
3
4
5
6
m 1
m 2
m 3
m 4
m 5
m 6
M 1
M 2
M 3
M 4
M 5
M 6

Saída

+ min 21
+ min 9
+ min 5
+ min 6
+ min 7
+ min 1
+ max 21
+ max 12
+ max 9
+ max 10
+ max 11
+ max 6

Exemplo 2
Entrada

20
-1434065850
-433067613
310970511
-549619948
-1451550805
412383783
-875452179
-651989905
-2004504033
-64436790
-43377078
-1106058583
144657761
7341370
14376750
-270108130
46786801
2068250020
974247051
-699904868
m 1
M 1
m 2
M 2
m 7
M 17

Saída

+ min -5605121735
+ max -5605121735
+ min -8337136225
+ max 2732014490
+ min -4155959706
+ max 2480633803