贪心

题目要求尽量最大的字典序，且每个元素最多只能交换两次。字典序是从前面开始比较的，因此我们也要从前面开始贪心，枚举到第i个的时候，记录max为当前元素，然后往下考虑终止条件就是他的次数足够换到第i个数(j-i<=cnt[j])并记录max，然后从max元素的下标连续交换到i即可

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
#define N 200005
int a[N];

题目内容

给出一个大小为$N$的数组，数组中的数仅由$1$~$N$组成，且没有重复的元素。

你可以选择相邻两个数进行交换，前提是，每个数最多只能被交换两次。

经交换后，所能形成的最大字典顺序的数组是多少?

从第一个数字开始，逐个元素比较直到找到第一个不同的数字，通过比较这个数字的大小决定序列的大小，称为字典顺序。

输入描述

输入的第一行给出数组的大小$N(1≤N≤10^5)$

随后$N$个数$x_i$。

$1 ≤ x_i≤ N$。

输出描述

输出所能形成的最大字典顺序的数组(每个数用空格分隔)

样例1

输入

8
3 7 2 1 6 5 4 8

输出

7 3 6 5 2 1 8 4