Reconstruyendo la muralla
Villa Rotejos ha presumido durante siglos de la muralla romana que rodea su casco antiguo. Por desgracia, las últimas décadas de presión urbanística han hecho que constructores sin escrúpulos destrocen nuestro patromonio cultural quitando, con nocturnidad y alevosía, piedra a piedra de la parte de arriba de muchas zonas, para utilizarlas en sus nuevas construcciones.
El resultado es que cada sección de la muralla tiene una altura distinta, dependiendo de cuánto haya sido atacada por los vándalos. A nadie se le escapa que la única zona a la que no le falta ni una sola piedra y mantiene su altura original es la que se ve desde la ventana del alcalde.
Afortunadamente en las últimas elecciones ha habido relevo generacional y el nuevo alcalde, Armando Mura Llitas, está decidido a recuperar el antiguo esplendor, igualando la altura de toda la muralla a la de su sección más alta. Desgraciadamente el presupuesto es reducido, y lo irá haciendo poco a poco según vaya consiguiendo los fondos.
Tras anunciarlo en el pregón, el buzón del Ayuntamiento se ha llenado de solicitudes de los vecinos, cada uno pidiendo que se comience la restauración por la parte que se ve desde su ventana.
Entrada
El programa deberá leer, de la entrada estándar, un primer número indicando cuántos casos de prueba tendrán que procesarse. Cada uno comienza con un número 1 ≤ N ≤ 500.000 con la longitud, en número de piedras, de la muralla. A continuación aparecen N números con el número de piedras a lo alto que aún quedan en la muralla en cada sección (hasta 2×109).
Después viene un número Q con el número de solicitudes de los vecinos que han llegado al Ayuntamiento, seguido de una línea por cada una, describiéndola. Todas las solicitudes están compuestas por dos números, 1 ≤ A ≤ B ≤ N, con el punto de inicio y final de la muralla que el vecino en cuestión quiere que se arregle primero.
Salida
El programa deberá escribir, para cada consulta, el número de piedras que se necesitarían para reconstruir la sección solicitada de modo que alcance la misma altura que la parte más alta de la muralla.
Después de cada caso de prueba se escribirá una línea con tres guiones (---).
Entrada de ejemplo
2 5 3 4 2 5 1 4 1 1 1 2 3 4 3 5 3 0 0 0 1 1 3
Salida de ejemplo
2 3 3 7 --- 0 ---