Se da una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$. Escribe un programa que realice las siguientes consultas:

• $1$ $i$ $j$ $x$ $y$: Suma la progresión aritmética con primer término $x$ y diferencia común $y$ a $A_i, A_{i+1}, \ldots, A_j$. ($1 \le i \le j \le N$, $-100{,}000 \le x, y \le 100{,}000$)
• $2$ $i$ $j$: Imprime la longitud de la subsecuencia continua más larga tal que $i \le l < r \le j$ y $A_l, A_{l+1}, \ldots, A_r$ forman una progresión aritmética. ($1 \le i < j \le N$)

Entrada

La primera línea contiene el tamaño de la secuencia $N$ ($2 \le N \le 100{,}000$).

La segunda línea contiene $A_1, A_2, \ldots, A_N$. ($-100{,}000 \le A_i \le 100{,}000$)

La tercera línea contiene el número de consultas $M$ ($1 \le M \le 100{,}000$).

Las siguientes $M$ líneas contienen las consultas.

Todos los valores de entrada son enteros.

Salida

Para cada consulta de tipo $2$, imprime la respuesta en una línea separada.

Ejemplos

Entrada 1

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

Salida 1

5
3
2