\{1, 2, … , N\}的排列 给出了 (p(1), p(2), … , p(n)) 。 由 (l_i, r_i) 组成的查询 给出了 Q ,因此对每个查询使用以下伪代码输出处理结果。
- ret := 0, (x(1), x(2), … , x(N)) := (1, 2, … , N) 。 关于
- 各i ∈ \{1, 2, … , N\} 关于 y(i) := p(x(i)) 。
- 各i ∈ \{1, 2, … , N\} 关于 x(i) = y(i)。
- ret := ret + x(l_i) + x(l_i+1) + … + x(r_i)
- 如果 (x(l_i), x(l_i+1), … , x(r_i)) = (l_i, l_i+1, … , r_i) 如果 (ret 模组 输出 10^9+7) 并退出。如果不是,则返回流程2。
入力形式
输入按以下格式给出
N Q p(1) p(2) ... p(N) l_1 r_1 ... l_Q r_Q
出力形式
一次一行打印每个查询的输出。 它是
制約
- 1 ≤ N ≤ 10^5
- 1 ≤ Q ≤ 10^4
- (p(1), p(2), … , p(N)) 是 (1, 2, … , N) 的排列。 对于
- 各 i ,有 1 ≤ k ≤ 40 存在,p^k(i)=i 变为。在这里, 在p^k(i) 是 p(p(p(… p(i)… ))) 出现 p 是 它可能以 k 次的东西。
- 1 ≤ l_i ≤ r_i ≤ N
入出力例
入力例 1
5 2 5 1 2 3 4 1 1 2 4
出力例 1
15 45
伪代码中的排列(x(1), x(2), … , x(N))更改如下。
1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1 1 2 3 4 5
入力例 2
10 5 3 1 2 5 4 10 6 7 9 8 1 10 1 5 3 3 5 10 9 10
出力例 2
660 90 6 178 67