1324: 主很在乎（hard version）
Memory Limit：512 MB
Time Limit：1.200 S
Judge Style：Text Compare
Creator：
Submit：58
Solved：4
Description
由于三体世界拥有三颗太阳，受三体问题影响，太阳运行轨道不稳定，无法计算。当行星被一颗太阳的引力所捕获而围绕其作规律运动时，称之为恒纪元，此时太阳升降规律；当行星在三颗太阳的引力间波动，做不规律运动时，称之为乱纪元，此时气温与光照变化不定，会发生各种灾难。三体人通过集体脱水度过乱纪元，在恒纪元集体苏醒，发展文明。
在某个恒纪元，三体人通过观察某颗恒星闪烁的频率得到了一串递增的数字，但不巧的是，因为某些原因这串数字被打乱了。不知道下一个乱纪元会在什么时候到来，时间紧迫的三体人请求你将这串数字复原。
注：本题与简单版的区别在于数据范围
Input
有两行
第一行一个数字n，代表这串数字有n个数（1≤n≤$6*10^{6}$ ）
第二行有n个数$a_{1}$, $a_{2}$, ..., $a_{n}$ (-1000≤$a_{i}$≤1000)，代表这串数字被打乱后的顺序
第一行一个数字n，代表这串数字有n个数（1≤n≤$6*10^{6}$ ）
第二行有n个数$a_{1}$, $a_{2}$, ..., $a_{n}$ (-1000≤$a_{i}$≤1000)，代表这串数字被打乱后的顺序
Output
一行，这串数字原本的顺序
Sample Input Copy
5
2 3 1 5 4Sample Output Copy
1 2 3 4 5HINT
请用更快的输入输出方法，如果不会使用scanf/printf，请使用以下模板：
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//从这里开始编写程序
}