Migrated from Lutece 3117 你好，然后，晚安～

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tags: 后缀系列，分类讨论

祝贺各位进入了暑假一轮集训。本次专题为制胡窜专场，希望您在本次专题中玩的愉快。

所以，我要睡觉了，这道题就你来帮我写了吧。

有一个长度为 $n$ 的字符串 $S$，现在被人随机剪成了三个非空的部分$^1$。lh3k 想要知道，对于原串中的一个子串 $S[l,r]$，其还存在$^2$于这三个部分中任意一个的概率是多少。

你需要回答 $q$ 次询问，且只需要输出在 $\bmod\ 998244353$ 意义下的答案即可。

$^1$更加严谨的，即等概率随机选取两个整数 $1\le p\lt q\lt n$，将 $S$ 划分为 $S[1,p]+S(p,q]+S(q,n]$ 三个不相交的部分。

$^2$一个字符串 $S$ 存在于另一个字符串 $T$ 当且仅当存在 $\exist i\text{ s.t. } S=T[i,i+|S|)$ 。

Input

输入数据的第一行包含一个整数 $n\ (3\le n\le 3\times10^5)$，紧接着的一行包含一个包含 $n$ 个整数 $S[1],S[2],..,S[n]\ (1\le S[i]\le n)$，表示字符串 $S$。（请注意，字符串 $S$ 的字符集大小为 $n$）

第三行包含一个整数 $q\ (1\le q\le 3\times10^5)$，表示询问次数。接下来的 $q$ 行每行包含两个整数 $l,r\ (l\le r)$，表示询问的子串是 $S[l..r]$。

Output

对于每次询问，输出一个整数，表示询问的答案。

Samples

5
1 1 2 1 1
3
1 1
2 3
4 5

1
499122177
831870295

10
3 3 1 3 2 1 1 1 3 3
10
6 7
6 10
4 7
1 2
1 7
3 8
10 10
7 9
4 10
2 2

138645050
610038216
915057324
138645050
582309206
166374059
1
83187030
582309206
1

3
1 1 1
1
1 3

0

Constraints

$3\le n\le 3\times10^5$

$1\le q\le 3\times10^5$

$1\le S[i]\le n$

Resources

2024 UESTC ICPC Training for String