#P9781. 嘉然

    ID: 6411 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-欧拉函数莫比乌斯函数线性筛倍数枚举单调栈有限候选集缩减离线查询树状数组

嘉然

题目描述

给定 11 到 nn 的一个排列 p1,…,pnp_1,\ldots,p_n。对于每个给出的区间 [l,r][l,r],求

max⁡l≤i<j≤rφ(pipj),\max_{l\le i<j\le r}\varphi(p_i p_j),

其中 φ\varphi 表示欧拉函数。

输入格式

第一行一个正整数 nn。 第二行给出排列 pp。 第三行一个正整数 qq。 接下来 qq 行,每行两个正整数 l,rl,r。

输出格式

输出 qq 行,每行一个整数,表示对应询问的答案。

样例输入

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×1051\le n,q\le 5\times10^5,1≤l<r≤n1\le l<r\le n。

本题采用捆绑测试。原题子任务如下。

子任务 n≤n\le q≤q\le 特殊性质 分值
1 500 无 5
2 3000 5×1055\times10^5
3 5×1055\times10^5 1 10
4 5×1045\times10^4 数据随机 15
5 2×1052\times10^5 20
6 5×1055\times10^5 pi=ip_i=i 15
7 无 30

原 PDF 题面