题目描述
嘉然今天吃欧拉函数。
给定一个长为 n 的排列 p ，q 组询问。每组询问给定 l, r ，请求出：

输入格式
第一行一个正整数 n ，表示排列长度。
第二行 n 个正整数，表示这个排列。
第三行一个正整数 q ，表示询问次数。
接下来 q 行，每行两个正整数，表示每组询问的 l 和 r 。
输出格式
输出 q 行，每行一个正整数，表示每组询问的答案。
样例输入
详见选手文件夹下的 diana/diana .in 文件。
样例输出
详见选手文件夹下的 diana/diana .out 文件。
数据规模与约定
本题采用捆绑测试，共 7 个 subtask，你必须通过每个 subtask 中的所有测试点才 能获得该 subtask 的分数。

对于全部数据，满足$ 1 ≤ n, q ≤ 5 × 10^5, 1 ≤ l < r ≤ n$。