Vé VIP Cổng Ngựa Bình Dương

Mô tả

Tại trường đua ngựa Bình Dương, ban tổ chức phát vé VIP cho khán giả theo danh sách ban đầu đã sắp xếp từ số thứ tự 1 đến n. Mỗi khách nhận một số thứ tự duy nhất.

Cổng kiểm soát chỉ có một cửa chính và một làn phụ chật hẹp. Làn phụ hoạt động giống như một ngăn xếp: khách vào theo thứ tự ban đầu, ai có thể đi thẳng qua cổng thì đi, ai chưa đến lượt phải đứng tạm trong làn phụ. Khách đứng sau cùng trong làn phụ sẽ được ra trước khi đến lượt.

Ban tổ chức muốn xác nhận xem một trình tự khách thực tế qua cổng cho trước có hợp lệ hay không. Bạn cần mô phỏng quá trình và kiểm tra.

Đầu vào

• target: danh sách gồm n số nguyên dương phân biệt, mỗi giá trị từ 1 đến n, đại diện cho trình tự khách thực tế qua cổng.

Đầu ra

• Trả về true nếu trình tự hợp lệ, ngược lại trả về false.

Ràng buộc

• 1 <= n <= 10^5
• target là hoán vị của các số từ 1 đến n.

Ví dụ

Ví dụ 1:

• Đầu vào: target = [2, 1, 3]
• Đầu ra: true

Giải thích: Khách ban đầu theo thứ tự [1, 2, 3].

• Đưa khách 1 vào làn phụ.
• Khách 2 đi thẳng qua cổng.
• Khách 1 ra khỏi làn phụ qua cổng.
• Khách 3 đi thẳng qua cổng. Kết quả hợp lệ.

Ví dụ 2:

• Đầu vào: target = [3, 1, 2]
• Đầu ra: false

Giải thích: Khách ban đầu theo thứ tự [1, 2, 3].

• Đưa khách 1 vào làn phụ, đưa khách 2 vào làn phụ.
• Khách 3 đi thẳng qua cổng.
• Lúc này đầu làn phụ là khách 2, nhưng trình tự yêu cầu khách 1 ra trước, nên không khớp. Trả về false.