{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"Jorge, el Oso Perezoso, encontró una colonia de $n$ hormigas ordenadadas en una fila. La $i$-ésima hormiga tiene fuerza $f_i$.\n\nPara hacer su cena más interesante, Jorge organizó un juego llamado Hormiga Battle Royale para las pobres hormigas. Él escoge dos números $l$ y $r$ $(1 \\leq l \\leq r \\leq n)$ y hace que todos los pares de hormigas con índices entre $l$ y $r$ peleen entre sí.\n\nCuando dos hormigas de índices $i$ y $j$ pelean, la hormiga $i$ obtiene un punto si y solo $f_i$ divide a $f_j$. De la misma forma, la hormiga $j$ obtiene un punto si y solo si $f_j$ divide a $f_i$.\n\nAl terminar todas las batallas, Jorge crea un ranking. Si la hormiga $i$ obtuvo $v_i$ puntos en total, será liberada solo si $v_i \u003d r-l$. En otras palabras, si obtuvo un punto en todas las peleas en las que participó. Después de eso, Jorge se come al resto de las hormigas.\n\nPara poder escoger la mejor secuencia $l, r$, Jorge te dará $q$ segmentos $[l_i, r_i]$ y para cada uno te preguntará cuántas hormigas se comerá si escoge ese segmento."}},{"title":"Entrada","value":{"format":"MD","content":"La primera línea contiene un entero $n$ $(1 \\leq n \\leq 10^5)$, el tamaño de la colonia de hormigas.\n\nLa segunda línea contiene $n$ enteros $f_1, f_2, \\dots, f_n$ $(1 \\leq f_i \\leq 10^9)$, indicando la fuerza de cada hormiga.\n\nLa tercera línea contiene un entero $q$, la cantidad de preguntas.\n\nCada una de las siguientes $q$ línea contiene dos enteros $l_i$ y $r_i$ $(1 \\leq l_i \\leq r_i \\leq n)$, describiendo una pregunta."}},{"title":"Salida","value":{"format":"MD","content":"Imprime $q$ líneas. En la $i$-ésima de ellas debes indicar cuántas hormigas Jorge comerá si escoge el segmento $[l_i, r_i]$."}},{"title":"Ejemplo 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eEntrada\u003c/th\u003e\n \u003cth\u003eSalida\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1 3 2 4 2\n4\n1 5\n2 5\n3 5\n4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n4\n1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Explicación","value":{"format":"MD","content":"En la primera pregunta, los puntos de las hormigas son $v \u003d [4, 0, 2, 0, 2]$, así que la primera hormiga será liberada y Jorge comerá a las otras 4.\n\nEn la segunda pregunta, los puntos son $v \u003d [0, 2, 0, 2]$, así que ninguna hormiga será liberada y Jorge comerá a las 4.\n\nEn la tercera pregunta, los puntos son $v \u003d[2, 0, 2]$, así que las hormigas 3 y 5 son liberadas, y se comerá solo a la hormiga 4.\n\nEn la cuarta pregunta los puntos son $v \u003d [0, 1]$, así que la hormiga 5 es liberada. Jorge se come a la hormiga 4."}}]}