该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一款战争游戏中，一些玩家自立为王，建立了王国，而每一个王国都是紧挨着的，它们都有各自的编号，从 $1$ 到 $n$ ，只有编号相邻的国家才能打仗，他们之间打仗必定会有一个国家灭亡，此时的各个国家的编号按从小到大重新赋予新的编号，比如原先各个国家的编号分别为: $1$ $3$ $4$ $6$ $8$ $9$ ,重排后变为 $1$ $2$ $3$ $4$ $5$ $6$ ,即原先的 $3$ 变为 $2$ ,原先的 $4$ 变为 $3$ ,原先的 $6$ 变为 $4$ ，原先的 $8$ 变为 $5$ ，原先的 $9$ 变为 $6$ ,每一次变化后国家与国家编号的大小关系不变，且编号为由 $1$ 开始的连续自然数，每打完一次仗就重排一次编号，一次只能打一场仗，所以上面的例子是不存在的。

战争规则是这样的： 双方猜拳确定胜负，胜利的国家威力变为两个国家之积，失败的国家灭亡。

打完仗后，获胜的国家会被复制，复制出来的国家会与某神秘国度（初始威力为 $1$ ）打仗，如果复制的国家赢了，则它回取代神秘国度，成为新的神秘国度，与下一次复制出来的国家打仗。

现在，只有原始编号为 $l_i\sim r_i$ 会打仗，请问这些国家打完仗后的神秘国度的威力最大为多少？

输入格式

第一行一个整数 $n$ 。

接下来 $n$ 个整数，第 $i$ 个整数表示原使编号为 $i$ 的国家士兵融合前的威力 $a_i$ 。

接下来一个整数 $q$ 。

接下来 $q$ 行，每行两个整数 $l_i,r_i$ 。

输出格式

共 $q$ 行，每行一个整数，表示剩下的国家最大威力是多少，由于答案可能很大，你只需要输出答案对 $114514$ 取模的结果即可。

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

36
1200
1

提示

对于 $60\%$ 的数据，满足 $1\le n,q\le 10$,$1\le a_i\le2$,$1\le l_i,r_i\le n$ 。

对于 $100\%$ 的数据，满足 $1\le n,q\le 10^2$,$1\le a_i\le10^9$,$1\le l_i,r_i\le n$ 。

【#样例解释】

以下解释使用原编号，隐藏胜利国家的复制品与神秘国家打仗的环节。

对于第一组询问，先让 $3$ 和 $2$ 打仗，获胜国家威力为 $6$ ,神秘国度威力变为 $6$ ,再让 $1$ 和胜利国家打仗，此时获胜国家威力为 $6$ ,神秘国度威力变为 $36$ 。此时神秘国度威力为 $36$ ，可以证明不能再强了。

对于第二组询问，先让 $4$ 和 $5$ 打仗，再让 $3$ 打仗，此时神秘国度威力为 $1200$ ，可以证明不能再强了。

对于第三组询问，只有 $5$ 一个国家，不打仗，神秘国度也不打仗，所以为 $1$ 。

来源

题目来自 BPOJ Round1。