P17899 [ICPC 2026 Nanchang I] Little Z's Function

Description

Little Z was obsessed with number-theoretic functions such as Euler's totient function $\varphi$ (Note: $\varphi(n)$ denotes the number of positive integers not exceeding $n$ that are coprime to $n$.) back in high school. One day, Little Z decides to play a game with his robotic friend. First, Little Z gives a permutation (Note: A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).) $p$ of length $n$. Then he asks his friend multiple queries. For a given interval $[l, r]$ ($1 \le l < r \le n$), find the maximum value of $\varphi(p_i \times p_j)$ where $l \le i < j \le r$. Formally, for each query with two integers $l, r$, you need to compute: $$ \max_{l \le i < j \le r} \varphi ( p_i \times p_j ) $$ Little Z has solved exactly $0$ queries. Please help him compute the remaining $q$ queries.

Input Format

The first line contains a positive integer $n$ ($2 \le n \le 5 \times 10^5$) --- the length of the permutation. The second line contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) --- the given permutation $p$. The third line contains a positive integer $q$ ($1 \le q \le 5 \times 10^5$) --- the number of queries. Each of the next $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i < r_i \le n$) --- the endpoints of the $i$-th query.

Output Format

For each query, output a single integer --- the maximum value.