UOJ Logo Universal Online Judge

UOJ

#186. 【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$ 的子序列。

样例一

input

4
1 2 4 3
2
1101
0011

output

1
3

explanation

第一组数据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$。

样例二

input

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

output

3

explanation

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

样例五

input

2
1 2
2
01
10

output

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}$

下载

样例数据下载