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:

• Dòng đầu tiên gồm số nguyên dương \(N\ \left( N\ \leq 10^{5} \right)\) 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} \leq \ 10^{9};\ 1\ \leq i\ \leq N\));

• Dòng thứ ba gồm một số nguyên dương \(Q\) là số lượng truy vấn \((Q\ \leq 10^{5})\);

• \(Q\) dòng sau, mỗi dòng gồm một số nguyên dương \(T\ (T\ \leq \ 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ả:

Gồm \(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.

Ràng buộc:

• Có \(50\%\) số test ứng với \(50\%\) số điểm của bài thoả mãn: \(N\ \leq 1000;Q = 1\);

• \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thoả mãn: \(N\ \leq \ 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.

Ví dụ: