题目描述
给定 1 到 n 的一个排列 p1,…,pn。对于每个给出的区间 [l,r],求
l≤i<j≤rmaxφ(pipj),
其中 φ 表示欧拉函数。
输入格式
第一行一个正整数 n。
第二行给出排列 p。
第三行一个正整数 q。
接下来 q 行,每行两个正整数 l,r。
输出格式
输出 q 行,每行一个整数,表示对应询问的答案。
样例输入
6
3 2 5 4 1 6
8
4 5
2 6
3 5
2 3
3 4
1 5
4 5
2 6
样例输出
2
8
8
4
8
8
2
8
数据规模与约定
对于所有数据,1≤n,q≤5×105,1≤l<r≤n。
本题采用捆绑测试。原题子任务如下。
| 子任务 |
n≤ |
q≤ |
特殊性质 |
分值 |
| 1 |
500 |
无 |
5 |
| 2 |
3000 |
5×105 |
| 3 |
5×105 |
1 |
10 |
| 4 |
5×104 |
数据随机 |
15 |
| 5 |
2×105 |
20 |
| 6 |
5×105 |
pi=i |
15 |
| 7 |
无 |
30 |
原 PDF 题面