Cây Phân Hoạch Theo Giá Trị Nhỏ Nhất · canuc80k7606

Cho dãy $a_{0}, a_{1}, \dots, a_{n - 1}$ gồm các số nguyên đôi một khác nhau. Cây Cartesian nhỏ nhất của dãy là cây nhị phân có các đỉnh $0, \dots, n - 1$ , đồng thời thỏa mãn:

khi duyệt cây theo thứ tự trung thứ tự (trái, gốc, phải), ta gặp các đỉnh theo đúng thứ tự $0, 1, \dots, n - 1$ ;
giá trị tại mỗi đỉnh cha nhỏ hơn giá trị tại mọi đỉnh con của nó.

Hai điều kiện trên xác định duy nhất một cây. Hãy tìm cha của từng đỉnh. Đối với gốc $r$ , quy ước cha của gốc là chính nó.

Input

Dòng đầu chứa số nguyên $n$ . Dòng thứ hai chứa $n$ số nguyên $a_{0}, a_{1}, \dots, a_{n - 1}$ .

Output

In $n$ số nguyên $p_{0}, p_{1}, \dots, p_{n - 1}$ , trong đó $p_{i}$ là cha của đỉnh $i$ .

Constraints

$1 \leq n \leq 1 0^{6}$ .
$0 \leq a_{i} \leq 1 0^{9}$ .
Các giá trị $a_{i}$ đôi một khác nhau.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

5
8 3 6 1 5

Output

1 3 1 3 3

Giải thích: Giá trị nhỏ nhất là $1$ tại đỉnh $3$ , nên $3$ là gốc. Đoạn bên trái có gốc $1$ , đoạn bên phải chỉ có đỉnh $4$ ; tiếp tục áp dụng cùng quy tắc cho từng đoạn sẽ thu được các quan hệ cha như kết quả.

Mô hình cây: Trong mọi đoạn liên tiếp, vị trí có giá trị nhỏ nhất phải là gốc của cây con biểu diễn đoạn đó. Vì thế khi thêm phần tử từ trái sang phải, chỉ đường đi từ gốc tới đỉnh ngoài cùng bên phải có thể thay đổi.
Thuật toán: Duy trì một stack chứa đúng đường đi phải của cây Cartesian của prefix đã xử lý, với giá trị tăng dần từ đáy lên đỉnh. Khi xét vị trí i, lấy khỏi stack mọi đỉnh có giá trị lớn hơn a_i. Gốc của phần vừa lấy ra trở thành con trái của i; nếu stack vẫn còn phần tử thì đỉnh stack là cha của i. Sau đó đưa i vào stack.
Chứng minh đúng đắn: Ta quy nạp theo độ dài prefix. Trước khi thêm i, stack là đường đi phải của cây đúng. Các đỉnh bị lấy ra tạo thành một suffix liên tiếp trong thứ tự trung thứ tự và đều lớn hơn a_i, nên toàn bộ cây con ấy phải nằm bên trái i; đỉnh bị lấy ra cuối cùng là gốc của suffix đó. Phần tử còn lại trên đỉnh stack là vị trí gần nhất bên trái có giá trị nhỏ hơn a_i, nên nó là cha của i. Các cạnh khác không đổi, do đó invariant tiếp tục đúng. Cuối cùng đáy stack là gốc toàn cây và được gán làm cha của chính nó.
Độ phức tạp: Mỗi đỉnh được đưa vào và lấy khỏi stack nhiều nhất một lần, nên thời gian là O(n) và bộ nhớ là O(n).