### 问题描述 本题是《消息队列Ⅰ》的进阶版，唯一不同的是数据范围。 聊天软件的消息列表可以看作一个队列，时间越近的消息排在越前面。小明有 $n$ 个好友，编号为 $1$ ~ $n$。给出初始的消息队列，接下来给出 $q$ 个动作，每一次动作包含一个整数 $a$，表示小明给好友 $a$ 发一次消息。在发完消息后，好友 $a$ 变为消息队列的首位。 对于每次动作之前，输出好友 $a$ 在消息队列的第几位。( 首位从 $1$ 开始) ### 输入格式 输入第一行，包含一个整数 $n$。 接下来一行，包含 $n$ 个整数，表示初始队列。 第三行，包含一个整数 $q$。 接下来 $q$ 行，每行一个整数表示一次动作。 ### 输出格式 对于每次动作，输出一个整数表示：好友 $a$ 在消息队列的第几位。 ### 样例输入 ```text 5 1 2 3 4 5 6 3 4 3 5 1 1 ``` ### 样例输出 ```text 3 4 2 5 4 1 ``` ### 说明 在样例中，初始消息队列为：$1, 2, 3, 4, 5$。 第一次动作前，好友 $3$ 在队列的第 `3` 位，动作后队列为：$3, 1, 2, 4, 5$。 第二次动作前，好友 $4$ 在队列的第 `4` 位，动作后队列为：$4, 3, 1, 2, 5$。 第三次动作前，好友 $3$ 在队列的第 `2` 位，动作后队列为：$3, 4, 1, 2, 5$。 第四次动作前，好友 $5$ 在队列的第 `5` 位，动作后队列为：$5, 3, 4, 1, 2$。 第五次动作前，好友 $1$ 在队列的第 `4` 位，动作后队列为：$1, 5, 3, 4, 2$。 第六次动作前，好友 $1$ 在队列的第 `1` 位，动作后队列为：$1, 5, 3, 4, 2$。 ### 评测数据规模 对于 $50$% 的评测数据，$1\leq n,q \leq 1\times 10^3$。 对于 $100$% 的评测数据，$1\leq n,q \leq 1\times 10^6$。