Cây Li Chao bền vững (Persistent Li Chao Tree) hỗ trợ truy vấn trên các phiên bản lịch sử.

Định dạng đầu vào

• Dòng 1: Số thao tác \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp theo chứa các thao tác tạo phiên bản mới hoặc truy vấn trên phiên bản cũ.

Định dạng đầu ra

• Kết quả tương ứng của từng truy vấn giá trị.

Ví dụ

Input:

3
1 0 2 3
2 1 2
2 0 2

Output:

7
0

Giải thích: Truy vấn trên các phiên bản lịch sử khác nhau.

Ràng buộc & Subtasks