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, ..., 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 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 tham gia mua bán bắt đầu từ ngày thứ T cho trước?

Dữ liệu: Đọc từ file VNI.INP gồm:

• Dòng 1: số nguyên dương N (N <= 10^5) là số ngày biết giá cổ phiếu;
  

• Dòng 2: gồm N số nguyên dương A_1, A_2, ..., A_N tương ứng là giá cổ phiếu VNI trong từng ngày (A_i <= 10^9; 1 <= i <= N);
  

• Dòng 3: số nguyên dương Q (Q <= 10^5) 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 mua bán cổ phiếu VNI.
  
  

Kết quả: Ghi ra file VNI.OUT

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:

• Subtask 1: có 50% số test tương ứng N <= 10^3; Q = 1
  

• Subtask 2: có 30% số test khác tương ứng N <= 10^5; Q = 1
  

• Subtask 3: có 20% test còn lạ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ới T = 1: Ngày 1 mua 1 cổ phiếu giá 1; Ngày 2 mua 1 cổ phiếu giá 2; Ngày 3 bán 2 cổ phiếu giá 5. Lợi nhuận: -1 - 2 + 2*5 = 7.
  
• Với T = 3: Bắt đầu từ ngày 3, giá ngày 3 là 5, ngày 4 là 4. Không nên mua vì giá giảm. Lợi nhuận = 0.