Giải bài trực tuyến

Một trong những cấu trúc dữ liệu nổi tiếng để lưu trữ dữ liệu là cây nhị phân tìm kiếm. Mỗi nút trên cây có nhiều nhất là hai nút con và nhiều nhất là một nút cha. Các nút con được chia thành hai loại: nút con trái và nút con phải. Mỗi cây tìm kiếm có một nút không có nút cha gọi là nút gốc, và có ít nhất một nút không có nút con gọi là nút lá. Mỗi một nút có gắn một giá trị nào đó thỏa điều kiện sau: Tại một nút v bất kỳ tất cả các giá trị thuộc cây con trái với gốc v nhỏ hơn giá trị tại nút v, và tất cả các giá trị ở các nút thuộc cây con bên phải với gốc v lớn hơn giá trị tại nút v.

Hình bên dưới mô tả một cây nhị phân tìm kiếm trong đó nút có giá trị 5 là gốc, các nút với giá trị 2, 4 và 8 là các nút lá.

Đường đi trên cây là dãy các giá trị tại các nút liên tiếp, trong đó mỗi nút sau là nút con trực tiếp của nút trước đó.

Yêu cầu: Cho một dãy gồm các giá trị đôi một khác nhau. Hãy cho biết tồn tại hay không cây tìm kiếm nhị phân, mà trên đó tồn tại một đường đi với dãy giá trị tương ứng là dãy đã cho.

Ví dụ, tồn tại cây nhị phân tìm kiếm với dãy 5 1 3 2, còn không tồn tại cây nhị phân tìm kiếm với dãy 5 2 3 1.

Dữ liệu

Lần lượt liệt kê các giá trị của dãy đã cho. Hai phân tử được ghi cách nhau bởi khoảng trắng hoặc dấu xuống dòng. Số lượng phần tử của dãy không vượt quá 50 000 và mỗi phần tử của dãy có giá trị tuyệt đối không vượt quá 2³¹.

Kết quả

Ghi ra từ “YES”, nếu tồn tại cây, tương ứng dãy đã cho hoặc từ “NO” trong trường hợp ngược lại.

Ví dụ

Dữ liệu
5 1 3 2	
Kết quả
YES

Dữ liệu
5 2 3 1	
Kết quả
NO