Mô tả và yêu cầu

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 n ngày đầu tiên lần lượt là a1, a2, ..,an. Biết rằng, mỗi ngày Bình
chỉ thực hiện một trong những hoạt động sau:
 Mua một cổ phiếu VNI.
 Bán số lượng cố phiếu bất kỳ mà Bình đang sở hữu.
 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 tham gia mua bán b ắt đầu từ ngày thứ T cho trước.
Dữ liệu: Vào từ thiết bị nhập chuẩn gồm
 Dòng 1: Số nguyên dương n (n ≤ 105) là số ngày biết giá cổ phiếu.
 Dòng 2: gồm n số nguyên dương a1, a2, ..., an tương ứng là giá cổ phiếu
VNI trong từng ngày (ai ≤ 109; 1 ≤ i ≤ n).
 Dòng 3: Số nguyên dương Q (Q ≤ 105) là số lượng truy vấn.
 Q dòng thiếp theo, mỗi dòng gồm một số nguyên dương T (T ≤ n) thể
hiện cho ngày đầu tiên mà Bình tham gia mua bán cổ phiếu VNI.
Kết quả: Ghi ra thiết bị xuất chuẩn gồm Q dòng, mỗi dòng 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.

Giới hạn và chấm điểm

 Subtask 1: có 50% số test tương ứng n ≤ 103, Q = 1;
 Subtask 2: có 30% số test tương ứng n ≤ 105, Q = 1;
 Subtask 3: có 20% số test còn lại không có ràng buộc gì thêm.

Ví dụ

INPUT               OUTPUT                               Giải thích
        4                      7                    * Bình bắt đầu mua bán VNI từ ngày 1:
        1 2 5 4                0                    Ngày 1: mua 1 VNI với giá 1
        2                                           Ngày 2: mua 1 VNI với giá 2
        1                                           Ngày 3: bán 2 VNI với giá 5
        3                                           Ngày 4: không tham gia giao dịch
                                                    Lợi nhuận thu được là: -1 -2 + 2*5 =7

                                                    * Bình bắt đầu mua bán VNI từ ngày 3:
                                                    Bình tham gia giao dịch và ngày thứ 3 và
                                                    ngày thứ 4.
                                                    Lợi nhuận thu dược bằng 0.