Dada una permutación ~p~ de ~n~ elementos. Procese ~q~ consultas de la forma:

• Dados ~a~, ~b~, ~c~ y ~d~ ~(1 \leq a \leq b < c \leq d \leq n)~, diga la cantidad de pares ~(x, y)~ tal que ~a \leq x \leq b~, ~c \leq y \leq d~ y ~p_x > p_y~.

Entrada:

La primera línea contendrá un entero ~n~, ~(2 \le n \le 6\,000)~, la cantidad de elementos de la permutación ~p~.

La segunda línea contendrá ~n~ enteros ~p_1, p_2, ... p_n~, los elementos de la permutación ~p~.

La tercera línea contendrá un entero ~q~, ~(1 \le q \le 500\,000)~, la cantidad de consultas.

Las siguientes ~q~ líneas contendrán cuatro enteros ~a~, ~b~, ~c~ y ~d~ ~(1 \leq a \leq b < c \leq d \leq n)~, la descripción de cada consulta.

Salida:

Imprima ~q~ líneas con un entero cada una, el resultado de cada consulta.

Subtareas:

• Subtarea 1: Para todas las consultas se cumple que ~a = b~ y ~c = d~, además ~n, q \leq 300~ (8 puntos)
• Subtarea 2: ~p = n, n-1, n-2, n-3, \cdots, 2, 1~, es decir, ~p~ es una permutación descendente, además ~n \leq 3000~ y ~q \leq 6\,000~ (11 puntos)
• Subtarea 3: ~n, q \leq 300~ (10 puntos)
• Subtarea 4: ~q \leq 6\,000~ (21 puntos)
• Subtarea 5: ~n \leq 3000~ (36 puntos)
• Subtarea 6: Sin restricciones adicionales (14 puntos)

Ejemplo de entrada:

6
1 6 2 5 3 4
4
1 2 4 6
2 4 6 6
1 4 5 6
1 1 2 6

Ejemplo de salida:

3
2
4
0