询问前P个数的最大值hard

这是一道一维数组例题，莫得什么难度，与easy版本不同的只是数据范围

题目描述

一开始第一行先输入一个$N$ $(1\leq N \leq 10^6)$

第二行输入$N$个整数，每个整数空格隔开，保证输入的数字为正整数且不超过$int类型$

接下来一行，输入一个整数$Q$ $(1\leq Q \leq N)$，表示有$Q$次询问

接下来$Q$行，每行一个整数$X$，表示需要查询的位置。

请你逐行打印每次查询的数组$1--X$位置存储的值的最大值是多少

然后按顺序依次输出这些数字，换行打印。

请用数组的方式来答题

样例

5
1 3 4 2 5
3
1
2
3

1
3
4

提示: 不要用双重循环来写