【UR #13】Yist
这里是跳蚤国中央广播电台，现在为您转播的是著名人类智慧大师 picks 博士与人工智能 betacome 之间的第一轮赛事。
这一场交锋的规则由网友 ma*****99 提供，这位网友也将获得由不想跳的跳蚤不是好跳蚤——最强跳蚤跳跳跳公司提供的金牌跳蚤一只。
今天晚上，我们也非常荣幸的邀请到了国内的人类智慧专家 AcrossTheSky 先生，A 先生您好。“主持人您好，观众朋友大家好。”
我们可以看到，第一轮的比赛已经开始了，A 先生您能给我们简要介绍一下这一轮比赛的规则吗？
“好的，我们可以看到，在 betacome 的屏幕上显示出了一个 排列 $A$ 以及它的一个 非空子序列 $B$，现在 picks 博士已经陷入了思考。在规则中，picks 博士需要给出一个 $x$ 并进行若干次操作，每一次操作他都需要在 $A$ 中选择一个长度恰好为 $x$ 的区间并删除它的最小值。如果在操作结束以后剩下的数组恰好是 $B$，那么 picks 博士就可以得到 $x$ 分，否则得到 $0$ 分。”
“可以看出来这个第一场的规则还是没有任何难度的，我们可以非常简单的就求出来 picks 博士能够得到的最高分。但是不知道为什么 picks 博士陷入了长考，我觉得他现在非常不在状态..”
那请问 A 先生，您可以看出来现在 picks 博士最多可以拿到多少分吗？
“呃...”
AcrossTheSky 发现他并没有办法快速的求得答案，于是他来向你寻求帮助，你可以帮帮他吗？
值得注意的是第一轮比赛中有 $q$ 道题目， 这 $q$ 道题目中的 $A$ 数组是完全一样的，但是选出的子序列 $B$ 却不一定相同，现在 AcrossTheSky 希望你能够把每一道题的答案都告诉他。
输入格式
第一行一个正整数 $n$，表示排列 $A$ 的长度。
接下来一行 $n$ 个数，表示排列 $A$。
接下来一行一个数 $q$。
接下来 $q$ 行，每行一个长度为 $n$ 的 01 串，如果第 $i$ 个位置是 $1$，则说明 $A$ 的第 $i$ 个位置的数出现在了 $B$ 中。
输出格式
输出 $q$ 行，每行一个整数，表示对每一道题目，picks 博士能够获得的最高分。
注意事项
对于给定 $n$，长度为 $n$ 且包含所有 $1$ 到 $n$ 中的整数的序列称为一个排列。
对于排列 $A$，对所有 $1 \le i_1 < i_2 < \cdots < i_k \le n$，称序列 $\{A_{i_1}, A_{i_2}, \cdots A_{i_k}\}$ 为 $A$ 的子序列。
4
1 2 4 3
2
1101
0011
1
3
第一组数据B序列为 $1\ 2\ 3$。
若 $x > 1$，则显然区间最小值不可能是最大的数 $4$，但是由于删除的数就是 $4$，所以 $x$ 必然是$1$。
第二组数据B序列为 $4\ 3$。
第一步只需要选定的区间包含 $1$，则可以删成 $2\ 4\ 3$。接下来只需要删除最小数 $2$。
由于题意中要求 $x \le n$ 才可以操作，所以 $x$ 最多只能到 $3$，而删除的是最小数所以 $x$ 显然可以等于 $3$。
10
2 3 8 9 4 5 7 6 1 10
1
1011111001
3
$B$ 序列为 $2\ 8\ 9\ 4\ 5\ 7\ 10$。
对于 $x = 3$ 一种可行的方案如下（加粗的数表示每次选择的区间）：
2 3 8 9 4 5 7 6 1 10
2 8 9 4 5 7 6 1 10
2 8 9 4 5 7 6 10
2 8 9 4 5 7 10
可以证明 $x = 4$ 的时候不存在可行的方案。
样例三
见样例数据下载。这个数据中 $n = 100$，$q = 5$。
样例四
见样例数据下载。这个数据中 $n = 100000$，$q = 5$。
2
1 2
2
01
10
2
1
限制与约定
对于 $30\%$ 的数据 $n \le 15$。
对于 $60\%$ 的数据 $n \le 1000$。
对于 $90\%$ 的数据 $n \le 300000$。
对于上述所有数据 $q \le 5$。
对于所有数据，$2 \le n \le 1000000$，$1 \le q \le 10$，$A$ 为一个排列，$B$ 为 $A$ 的非空子序列，且 $B \ne A$。
时间限制：$1\texttt{s}$
空间限制：$256\texttt{MB}$