#46. 西蒙的相亲大会

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: OrangeQWQ

题目描述

就这样,猫猫冒险队添加了两名新成员,黑客 Kiana 和小可莉 EricJC

夜色已经降临,不知道从哪里冒出来了个人,他说他叫小坑,想将大家带到他的村庄里休息一晚。

村庄的晚上十分热闹,村民们在举办《非橙勿扰》相亲节目,猫猫冒险队打算去吃瓜看戏。

一个名叫 Simon 的村姑最近春心荡漾,她想要个对象。然后她就去参加了相亲节目《非橙勿扰》

在《非橙勿扰》里有 个前来相亲的男生,每个男生都拥有魅力值 算法能力越强魅力值越高 )。

节目里拥有一个特殊的规则, Simon 如果在第 个男生上场之后上场,那么 Simon 只能选择前 个男生来亮灯(包括第 个)。

节目的上场顺序是抽签制,而狡猾的 Simon 偷偷黑入了节目内部,知道了她一共有 种不同的上场顺序。

Simon 想知道每种情况下自己的真命天子都是谁,请你帮她计算出每种情况下她能找到的最有魅力值的美男子。

输入格式

第一行一个正整数 ,代表前来相亲的男生总数。

第二行 个用空格分隔的正整数 ,代表第 个男生的魅力值。

第三行一个正整数 ,代表不同上场顺序的数目。

后面 行,每行一个正整数,代表 Simon 在第 个男生上场后上场。

输出格式

输出 行,一行一个正整数,代表在第 个男生上场后上场的 Simon 能找到的最大魅力值的男生。

样例

输入样例

9 
6 5 7 9 2 1 2 5 6
2
1
4

输出样例

6
9

数据范围与提示