Khoảng phủ của giá trị truy vấn

Bối cảnh

Một hệ thống log lưu n mã sự kiện theo thứ tự thời gian. Với một mã x, bộ phận phân tích không chỉ muốn biết x xuất hiện bao nhiêu lần mà còn muốn biết khoảng thời gian mà x "phủ" trên log: từ lần xuất hiện đầu tiên đến lần xuất hiện cuối cùng. Nếu x không xuất hiện, cả hai vị trí phải là -1.

Bài toán yêu cầu một lần duyệt đệ quy duy nhất. Mỗi tầng xử lý một index i: nếu a[i]==x, tăng count; nếu đây là lần đầu tiên thì ghi first=i; trong mọi lần khớp, cập nhật last=i. Sau đó chuyển sang i+1. So với bài đếm x cũ, người học phải duy trì ba thành phần trạng thái có quan hệ với nhau và xử lý đúng input n=0. Đây là dạng tổng hợp thông tin trên dãy thường gặp trong đề thi: yêu cầu không khó về thuật toán, nhưng dễ sai nếu khởi tạo sentinel hoặc cập nhật first/last không đúng.

Yêu cầu

1. Đọc n, mảng và x.
2. Dùng recursion duyệt mảng đúng một lần.
3. Tính count, first index, last index.
4. Nếu x không có, in 0 -1 -1; ngược lại in count first last.

Yêu cầu tổ chức code

Phần quét mảng bắt buộc dùng recursion.

Online Judge chấm output. Giảng viên có thể review source code để xác nhận học viên dùng đúng recursion và không vượt prerequisite.

Input

Dòng 1 n; dòng 2 có n số nếu n>0; dòng cuối x.

Output

Một dòng count first last.

Ràng buộc

0 ≤ n ≤ 3000, |a[i]|,|x| ≤ 10^9.

Ví dụ 1

Input

7
1 2 1 3 1 4 1
1

Output

4 0 6

Giải thích

Giá trị x=1 xuất hiện ở các index 0,2,4,6. Mỗi lần gặp, count tăng; first được gán 0 ở lần đầu và không đổi nữa; last được cập nhật lần lượt 0→2→4→6. Kết thúc recursion ta có count=4, first=0, last=6, nên output là 4 0 6.

Ví dụ 2

Input

5
1 2 3 4 5
9

Output

0 -1 -1

Giải thích

Mảng 1 2 3 4 5 không có phần tử nào bằng x=9. Recursion vẫn duyệt đủ các index 0 đến 4, nhưng ở mỗi tầng điều kiện a[i]==x đều sai nên count không tăng, first không được gán và last cũng không thay đổi. Khi i đạt n, base case dừng với state 0, -1, -1. Vì vậy output chính xác là 0 -1 -1.

Thông tin học tập

• Module: M04
• Buổi: B14
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: recursion, static arrays, occurrence count, first last index, reference state
• Giới hạn kiến thức: B01-B14
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100