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,\dots ,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 nhập 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,\dots ,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.

Ràng buộc

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

Ví dụ

Input

4
1 2 5 4
2
1
3

Output

7
0

Giải thích:

• Bình bắt đầu tham gia mua 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 $2$ VNI với giá là $5$.
  • Ngày $4$: không mua hay bán VNI vào ngày này.

$\Rightarrow$ Lợi nhuận thu được là: $-1-2+2\times 5=7$.

• Bình bắt đầu tham gia mua bán VNI vào ngày $3$:
  • Bình không mua bán VNI vào ngày $3$ và ngày $4$.

$\Rightarrow$ Lợi nhuận thu được là: $0$.