想定解よりも高速な解法として \(\mathrm{O}(N)\) 解法の概要を説明します。

区間 \([L, R]\) に対して、 \(P_{L, R}\) を次の条件を満たす列として定義します。(\(P_{L, R}\) はお気持ちとしては, 「\((a_L, \dots, a_R)\) から部分列を答えの順列に採用する時, 最終的に辞書順最小な順列が得られるように選んだ時の列」と言えます。)

• \((a_L, a_{L+1}, \dots, a_R)\) の非空な部分列のうち、全ての要素が異なる列からなる集合を \(S\) とする。
• 列 \(v\) に対して, 数列を無限数列へ移す関数 \(F\) を \(F(v) = (v_1, v_2, \dots, v_{|v|}, \infty, \infty, \dots)\) を満たすように定義する。このとき, \(S\) の要素 \(v\) のうち \(F(v)\) が辞書順最小であるような \(v\) を \(P_{L, R}\) と定義する。

また、\(p_{L, R}\) を同様に「 \((a_L, a_{L+1}, \dots, a_R)\) の中から、 \((a_1, \dots, a_{L-1})\) の区間において答えの順列に採用された値を取り除いてできる列に対して、上記の処理をして得られる列」と定義します。
詳細は想定解と被るので略しますが、\(p_{L, R}\) を利用すると、次の 2 つの操作を高速に行うことができれば 尺取り法のように 2 つのポインタを前から後ろへ移動していく要領でこの問題を \(\mathrm{O}(N)\) で解くことができます。

• \(p_{L, R}\) を \(p_{L, R+1}\) に更新する。
• \(p_{L, R}\) の先頭要素の元の数列 \(a\) における index を i として, \(p_{L, R}\) を \(p_{i, R}\) に更新する。

ここで \(p_{L, R}\) は、 \((a_L, \dots, a_R)\) から構成できる Cartesian Tree の、根から右方向の子へ再帰的に向かうパスと考えることができて(ただし同じ整数が複数回登場する場合は例外的な処理が必要です) 、\(p_{L, R}\) から \(p_{L, R+1}\) の計算はならし \(\mathrm{O}(1)\) で計算できます。
よってこの問題を全体で \(\mathrm{O}(N)\) で解くことができます。

• 実装例(C++)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A[i];

  vector<int> rightmost(M + 1, -1), ans, used(M + 1), path_used(M + 1);
  deque<int> Q;

  for (int i = 0; i < N; i++) rightmost[A[i]] = i;
  for (int j = 0; j < N; j++) {
    if (used[A[j]]) continue;
    if (!path_used[A[j]]) {
      while (!Q.empty() and A[Q.back()] > A[j]) {
        path_used[A[Q.back()]] = 0, Q.pop_back();
      }
      Q.push_back(j), path_used[A[j]] = 1;
    }
    if (rightmost[A[j]] == j) {
      while (used[A[j]] == 0) {
        int idx = Q.front();
        Q.pop_front(), path_used[A[idx]] = 0;
        ans.push_back(A[idx]), used[A[idx]] = 1;
      }
    }
  }
  for (int i = 0; i < M; i++) cout << ans[i] << " \n"[i + 1 == M];
}