Cổ phiếu VNI

Bình mua bán cổ phiếu VNI trên thị trường chứng khoán. Giả sử giá của một cổ phiếu VNI trong vòng $N$ ngày lần lượt là $A_1, A_2, \ldots, A_N$. Biết rằng mỗi ngày Bình chỉ thực hiện một trong những hoạt động sau:

1. Mua một cổ phiếu VNI;
2. Bán số lượng cổ phiếu VNI bất kì mà Bình đang sở hữu;
3. Không thực hiện bất kì giao dịch nào.

Yêu cầu: Bình thực hiện mua bán cổ phiếu VNI như thế nào để thu được lợi nhuận lớn nhất nếu anh ấy tham gia mua bán bắt đầu từ ngày thứ $T$ cho trước?

Dữ liệu vào từ file văn bản VNI.INP:

• Dòng đầu tiên gồm số nguyên dương $N$ ($N \le 10^5$) là số ngày biết giá cổ phiếu;
• Dòng thứ hai gồm $N$ số nguyên dương $A_1, A_2, \ldots, A_N$ tương ứng là giá của một cổ phiếu VNI trong từng ngày ($A_i \le 10^9$; $1 \le i \le N$);
• Dòng thứ ba gồm một số nguyên dương $Q$ là số lượng truy vấn ($Q \le 10^5$);
• $Q$ dòng sau, mỗi dòng gồm một số nguyên dương $T$ ($T \le N$) thể hiện cho ngày đầu tiên mà Bình tham gia việc mua bán cổ phiếu VNI.

Kết quả ghi ra file văn bản VNI.OUT: $Q$ dòng, mỗi dòng gồm một số nguyên duy nhất là lợi nhuận lớn nhất mà Bình thu được ở mỗi truy vấn tương ứng.

• Có 50% số test ứng với 50% số điểm của bài thoả mãn: $N \le 1000$; $Q = 1$;
• 30% số test khác ứng với 30% số điểm của bài thoả mãn: $N \le 10^5$; $Q = 1$;
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.