题目描述

在新年这个欢腾的 $vibe$ 之中，依然有一群孤单的人，而质数恰好又是公认的“孤单”的数字。

现有一排 $n$ 个人，每个人手中拿着一个数字 $a_i$，每个人的“孤单值”是 $1\sim a_i$ 中与 $a_i$ 互质的数字的个数。

现有 $q$ 个分组的派对方案，每组方案选取 $l,r$ 的范围，每组方案的评分是区间内“孤单值”为质数的人数。求问第几个分组方案评分最高。

输入格式

第一行，$1$ 个正整数 $n$。

第二行，$n$ 个正整数 $a_i$。

第三行，$1$ 个正整数 $q$。

接下来 $q$ 行，每行 $2$ 个正整数 $l_i,r_i$，表示当前方案的范围。

输出格式

$1$ 个正整数，在 $1\sim q$ 之间，表示评分最大的方案序号（有相同最大评分的输出最靠前的序号）。

输入输出样例

3 
3 2 1
2
1 2
2 3

1

样例 $\tt \#1$说明

• $3$ 人的“孤单值”分别为 $[2,1,0]$，在 $2$ 组方案中，第一组前两人的孤单值为质数的有 $1$ 人；第二组后两人的孤单值为质数的有 $0$ 人。因此第 $1$ 组方案评分最多。

数据范围

• 对于 $60\%$ 的数据，$n\le 10^3,q\le 10^3$
• 对于 $100\%$ 的数据，$1\le n\le 10^5, 1\le a_i\le 10^9,1\le q \le 10^5,1\le l_i\le r_i\le n$