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 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≤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,…,A_N~ tương ứng là giá của một cổ phiếu VNI trong từng ngày ~(A_i≤10^9; 1≤i≤N);~
• Dòng thứ ba gồm một số nguyên dương ~Q~ là số lượng truy vấn ~(Q≤10^5);~
• ~Q~ dòng sau, 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\%~ số test tương ứng với ~50\%~ số điểm thoả mãn: ~N≤1000; \ Q=1;~
• ~30\%~ số test khác tương ứng với ~30\%~ số điểm thoả mãn ~N≤10^5; \ Q=1;~
• ~20\%~ số test còn lại tương ứng với ~20\%~ 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~.