smallest Permutation

Cho một số nguyên n và một dãy số a với tính chất dãy a là một dãy con của một hoán vị n phần tử.

• Một dãy p(1), p(2), ..., p(n) được gọi là một hoán vị n phần tử nếu như các số từ 1 đến n sẽ xuất hiện trong p chính xác 1 lần.
  Ví dụ: với n = 3 thì dãy {1, 3, 2} được gọi là hoán vị n phần tử nhưng {1, 2, 2} thì không.
• Dãy con (subsequences) là một dãy có thể được tạo ra từ dãy ban đầu bằng cách xóa đi một số phần tử hoặc không phần tử nào mà không thay đổi thứ tự của các phần tử còn lại.
  Ví dụ: Với dãy ban đầu là {1, 3, 4, 2, 5} thì {1, 4, 2} là dãy con nhưng {1, 2, 4} thì không là dãy con.
• Xét 2 dãy A, B có cùng độ dài n thì dãy A được coi là dãy có thứ tự nhỏ hơn dãy B nếu tồn tại số k (1 <= k <= n) sao cho:
  • Với mọi i từ 1 đến (k - 1) thì A(i) = B(i)
  • A(k) < B(k)
    Ví dụ: {1, 3, 4, 2, 5} nhỏ hơn {1, 3, 5, 4, 2} với k = 3

Hãy tìm dãy hoán vị n phần tử mà chứa dãy a là một dãy con, nếu có nhiều đáp án thì tìm dãy hoán vị có thứ tự từ điển nhỏ nhất.

Ví dụ:

• Với n=5, a=[1,4,2] thì smallestPermutation(n, a) = [1,3,4,2,5]
  Giải thích: Các dãy hoán vị n phần tử theo thứ tự từ điển tăng dần sẽ chứa dãy {1, 4, 2} là dãy con là 
  {1, 3, 4, 2, 5} -> Đáp án
  {1, 3, 4, 5, 2}
{1, 3, 5, 4, 2}
{1, 5, 3, 4, 2}
{3, 1, 4, 2, 5}
...............
{5, 3, 1, 4, 2} -> Dãy có thứ tự từ điển lớn nhất

Đầu vào/Đầu ra:

• [Giới hạn thời gian chạy]: 0.5 giây với C++, 3 giây với Java và C#, 4s với Python, GO và Js.
• [Đầu vào] Integer n
  2 <= n <= 1000
  
• [Đầu vào] Array of Integer a
  1 <= a.length <= n
1 <= a[i] <= n
  Dữ liệu dảm bảo các số trong a đều phân biệt
• [Đầu ra] array.integer
  Dãy hoán vị n phần tử cần tìm.