这里是跳蚤国中央广播电台，现在为您转播的是著名人类智慧大师 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$ 的子序列。

样例一

input

4
1 2 4 3
2
1101
0011

output

1
3

explanation

第一组数据B序列为 $123$。

若 $x>1$，则显然区间最小值不可能是最大的数 $4$，但是由于删除的数就是 $4$，所以 $x$ 必然是$1$。

第二组数据B序列为 $43$。

第一步只需要选定的区间包含 $1$，则可以删成 $243$。接下来只需要删除最小数 $2$。

由于题意中要求 $x\le n$ 才可以操作，所以 $x$ 最多只能到 $3$，而删除的是最小数所以 $x$ 显然可以等于 $3$。

样例二

input

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

output

3

explanation

$B$ 序列为 $28945710$。

对于 $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$。

样例五

input

2
1 2
2
01
10

output

2
1

限制与约定

对于 $30\mathrm{\%}$ 的数据 $n\le 15$。

对于 $60\mathrm{\%}$ 的数据 $n\le 1000$。

对于 $90\mathrm{\%}$ 的数据 $n\le 300000$。

对于上述所有数据 $q\le 5$。

对于所有数据，$2\le n\le 1000000$，$1\le q\le 10$，$A$ 为一个排列，$B$ 为 $A$ 的非空子序列，且 $B\ne A$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载