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ừ tệp văn bản VNI.INP, gồm:

- Dòng đầu tiên gồm số nguyên dương N (N ≤ 10⁵) là số ngày biết giá cổ phiếu.
- Dòng thứ hai gồm N số nguyên dương A₁, A₂, …, A_N, tương ứng là giá của một cổ phiếu VNI trong từng ngày (A_i ≤ 10⁹; 1 ≤ i ≤ N).
- Dòng thứ ba gồm một số nguyên dương Q (Q ≤ 10⁵) là số lượng truy vấn.
- Q dòng tiế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 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.

Ràng buộc:

- Có 50% test ứng với 50% số điểm của bài thỏa mãn N ≤ 1000, Q = 1.
- Có 30% test ứng với 30% số điểm của bài thỏa mãn N ≤ 10⁵, Q = 1.
- Có 20% 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ụ:

VNI.INP
4
1 2 5 4
2
1
3

VNI.OUT
7
0

Giải thích ví dụ:

• Bình bắt đầu tham gia bán VNI vào ngày 1: Ngày 1: mua 1 VNI với giá là 1; Ngày 2: mua 1 VNI với giá là 2; Ngày 3: bán hai VNI với giá là 5; Ngày 4: không mua hay bán VNI vào ngày này. Lợi nhuận thu được là: -1 - 2 + 2 x 5 = 7.

• Bình bắt đầu tham gia mua bán VNI vào ngày 3: Bình không mua VNI vào ngày 3 và ngày 4. Lợi nhuận thu được là: 0.