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.