Tấm biển trên hàng rào (Sign on Fence)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Hàng rào có $n$ tấm liên tiếp, tấm $i$ cao $h_i$. Với mỗi truy vấn $l,r,w$, cần đặt một tấm biển hình chữ nhật rộng đúng $w$ tấm, nằm hoàn toàn trong các tấm $l..r$. Chiều cao biển không được vượt quá chiều cao của bất kỳ tấm rào nào mà nó phủ. Hãy tìm chiều cao lớn nhất có thể.

Dữ liệu vào

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ chiều cao. Dòng thứ ba chứa $m$. Mỗi trong $m$ dòng sau chứa $l,r,w$.

Kết quả

Với mỗi truy vấn, in chiều cao lớn nhất của tấm biển.

Subtask

Subtask 1 (20%)

• $n\le 30$, số truy vấn $\le 30$.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, số truy vấn $\le 3000$.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n,m\le10^5$
• $1\le h_i\le10^9$
• $1\le l\le r\le n$
• $1\le w\le r-l+1$

Ví dụ

Input

5
1 2 2 3 3
3
2 5 3
2 5 2
1 5 5

Output

2
3
1

Giải thích

Với truy vấn 2 5 3, ta cần ba tấm liên tiếp trong [2,5]. Chọn các tấm 2..4 có chiều cao [2,2,3], nên biển cao tối đa $2$.