题目背景

译自 ICPC 2024 Yokohama Regional Contest。

题目描述

给定一个整数序列和该序列上的若干区间。这些区间由其最左位置和最右位置指定。一个包含 $k$ 个整数的区间具有 $k(k - 1)/2$ 个位于不同位置的数对，每个数对有其最大公约数。 对于每个给定的区间，找出所有这些最大公约数中最大的一个。

例如，当序列为 $(a_1, \ldots, a_6) = (10, 20, 30, 40, 50, 60)$，且询问区间为整个序列时，需要考虑以下 $15$ 个位于不同位置 $x$ 和 $y$ 的两个整数组成的数对及其最大公约数：

在此例中，这 $15$ 个数对的最大公约数中的最大值为 $\gcd(30, 60) = 30$。

输入格式

仅一组数据，格式如下所示：

$n$
$a_1$ $\cdots$ $a_n$
$q$
$l_1$ $r_1$
$\cdots$
$l_q$ $r_q$

第一行包含一个整数 $n$，表示给定序列中整数的个数，满足 $2 \leq n \leq 10^5$。第二行包含 $n$ 个正整数 $a_1$ 到 $a_n$，指定该序列。其中每个数均不超过 $10^5$。

第三行包含一个正整数 $q$，指定要考虑的序列区间数量，其值不超过 $10^5$。 随后是 $q$ 行，每行指定序列中一个要考虑的区间。其中第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ $(1 \leq l_i < r_i \leq n)$，指定序列中从 $a_{l_i}$ 到 $a_{r_i}$ 的区间。

输出格式

输出 $q$ 行，其中第 $i$ 行应包含在 $l_i$ 和 $r_i$ 指定的区间内所有数对的最大公约数中的最大值。

6
10 20 30 40 50 60
3
1 6
2 5
4 5

30
20
10

10
13 2 35 4 13 2 5 1 7 4
5
1 4
4 10
3 8
3 9
1 10

2
4
5
7
13