Greatest of the Greatest Common Divisors

Time limit1sMemory limit2048 MB

Summary

Given an integer sequence and range queries, find the largest gcd over all pairs of positions inside each query range.

Level: Medium6 of 10
Topics: Number theory, Sorting, Array
Solved: No attempts yet

Problem

You are given a sequence of integers and a number of intervals in the sequence. The intervals are specified by their leftmost and rightmost positions. An interval consisting of $k$ integers has $k(k - 1)/2$ pairs of integers at different positions, and each pair has a greatest common divisor. For each given interval, find the greatest of these greatest common divisors.

For example, when the sequence is $(a_1, \dots , a_6) = (10, 20, 30, 40, 50, 60)$ and the whole sequence is the interval, the following 15 pairs of integers at different positions $x$ and $y$ are considered.

$x$	$1$	$1$	$1$	$1$	$1$	$2$	$2$	$2$	$2$	$3$	$3$	$3$	$4$	$4$	$5$
$y$	$2$	$3$	$4$	$5$	$6$	$3$	$4$	$5$	$6$	$4$	$5$	$6$	$5$	$6$	$6$
$a_x$	$10$	$10$	$10$	$10$	$10$	$20$	$20$	$20$	$20$	$30$	$30$	$30$	$40$	$40$	$50$
$a_y$	$20$	$30$	$40$	$50$	$60$	$30$	$40$	$50$	$60$	$40$	$50$	$60$	$50$	$60$	$60$
$\gcd(a_x,a_y)$	$10$	$10$	$10$	$10$	$10$	$10$	$20$	$10$	$20$	$10$	$10$	$30$	$10$	$20$	$10$

The greatest of the greatest common divisors of these 15 pairs is $\gcd(30, 60) = 30$ in this case.

Input

The input consists of a single test case. The first line contains an integer $n$ ( $2 \le n \le 10^5$ ), the number of integers in the sequence. The second line contains $n$ positive integers $a_1, \dots, a_n$ . None of them exceeds $10^5$ . The third line contains a positive integer $q$ ( $q \le 10^5$ ), the number of intervals. The next $q$ lines each contain two integers $l_i$ and $r_i$ ( $1 \le l_i < r_i \le n$ ), specifying the interval $a_{l_i}$ through $a_{r_i}$ .

Output

Output $q$ lines. The $i$ -th line contains the greatest of the greatest common divisors of all pairs in the interval specified by $l_i$ and $r_i$ .

Examples2

Example 1

Input

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

Expected output

30
20
10

Example 2

Input

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

Expected output