Đèn Tín Hiệu Ngã Tư Đà Nẵng

Mô tả

Ngã tư đường Trần Phú - Bạch Đằng ngay cầu Rồng Đà Nẵng có một cụm đèn tín hiệu lập trình sẵn. Ban kỹ thuật giao thông lưu lại một mảng a gồm n phần tử mô tả chu kỳ hoạt động: tại giây thứ 1 đèn hiển thị trạng thái a[0], giây thứ 2 hiển thị a[1], cứ thế lần lượt đến hết giây thứ n. Hết giây thứ n, chu trình quay lại từ đầu với trạng thái a[0] ở giây thứ n+1, và cứ thế lặp đi lặp lại mãi mãi.

Một ngày, một người bạn mong bạn giúp tính xem tại một thời điểm T (tính bằng giây, đếm từ 1) đèn đang báo màu gì. Đừng tính từng giây một nhé, hãy dùng toán học để trả lời nhanh nhất có thể.

Đầu vào

• Số nguyên n (1 ≤ n ≤ 10^5): số phần tử của mảng chu kỳ.
• Mảng a gồm n số nguyên dương, mỗi số nằm trong khoảng từ 1 đến 10^9 (giả định 1=Đỏ, 2=Xanh, 3=Vàng).
• Số nguyên T (1 ≤ T ≤ 10^9): thời điểm cần tra cứu (tính bằng giây, bắt đầu từ giây thứ 1).

Đầu ra

• Trả về một số nguyên duy nhất là trạng thái đèn tại thời điểm T.

Ràng buộc

• 1 ≤ n ≤ 10^5.
• 1 ≤ |giá trị phần tử| ≤ 10^9.
• 1 ≤ T ≤ 10^9.
• Độ phức tạp thời gian mục tiêu: O(1) cho mỗi truy vấn sau khi đã có mảng.

Ví dụ

Ví dụ 1:

• Đầu vào: n = 4, a = [1, 2, 3, 2], T = 7
• Đầu ra: 3
• Giải thích: Chu kỳ có 4 phần tử. Từ giây 1 đến 4 đèn lần lượt là 1, 2, 3, 2. Đến giây 5 chu trình lặp lại nên đèn là 1, giây 6 là 2, và giây 7 là 3. Bạn chỉ cần lấy (7-1) % 4 = 2, đối chiếu với mảng a ta ra ngay a[2] = 3.

Ví dụ 2:

• Đầu vào: n = 1, a = [1], T = 1000000000
• Đầu ra: