{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eTrong các lớp lập trình, Vasya được giao một bài toán khó. Tuy nhiên, anh ta không biết cách viết code và không thể tìm ra giải pháp trên Internet, vì vậy anh ấy yêu cầu bạn giúp đỡ.\u003c/p\u003e\u003cp\u003eBạn được cho một dãy số $$$a$$$, bao gồm $$$n$$$ số nguyên \u003cspan class\u003d\"tex-font-style-bf\"\u003ekhác nhau\u003c/span\u003e, được sử dụng để xây dựng cây tìm kiếm nhị phân. Dưới đây là mô tả hình thức của quá trình xây dựng.\u003c/p\u003e\u003col\u003e \u003cli\u003e Phần tử đầu tiên $$$a_1$$$ trở thành gốc của cây. \u003c/li\u003e\u003cli\u003e Các phần tử $$$a_2, a_3, \\ldots, a_n$$$ được thêm vào một cách tuần tự. Để thêm phần tử $$$a_i$$$, người ta cần duyệt cây bắt đầu từ gốc và sử dụng các quy tắc sau: \u003col\u003e \u003cli\u003e Con trỏ đến nút hiện tại được đặt ở gốc. \u003c/li\u003e\u003cli\u003e Nếu $$$a_i$$$ lớn hơn giá trị trong nút hiện tại, thì con phải của nó trở thành nút hiện tại. Ngược lại, con trái của nút hiện tại trở thành nút hiện tại mới. \u003c/li\u003e\u003cli\u003e Nếu tại một điểm nào đó không có con cần thiết, nút mới được tạo ra, nó được gán giá trị $$$a_i$$$ và trở thành con tương ứng của nút hiện tại. \u003c/li\u003e\u003c/ol\u003e \u003c/li\u003e\u003c/ol\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên của đầu vào chứa một số nguyên $$$n$$$ ($$$2 \\leq n \\leq 100\\,000$$$)\u0026nbsp;— độ dài của dãy số $$$a$$$.\u003c/p\u003e\u003cp\u003eDòng thứ hai chứa $$$n$$$ số nguyên khác nhau $$$a_i$$$ ($$$1 \\leq a_i \\leq 10^9$$$)\u0026nbsp;— dãy số $$$a$$$ chính nó.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eĐầu ra $$$n - 1$$$ số nguyên. Đối với tất cả $$$i \u0026gt; 1$$$ in ra giá trị được viết trong nút là cha của nút chứa giá trị $$$a_i$$$ trong đó.\u003c/p\u003e"}},{"title":"Ví dụ","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n4 2 3 1 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4 2 2 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}