Cổ phiếu VNI

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.

Mỗi truy vấn được xét độc lập: Bình bắt đầu từ ngày $T$ khi chưa sở hữu cổ phiếu nào và tham gia mua bán từ ngày $T$ đến hết ngày $N$. Lợi nhuận là tổng số tiền bán được trừ tổng số tiền đã bỏ ra mua.

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 vào

• 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.

Dữ liệu ra

Gồm $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

• $1\le N\le {10}^5$.
• $1\le A_i\le {10}^9$.
• $1\le Q\le {10}^5$.
• $1\le T\le N$.

Subtasks

• Có $50\%$ số test ứng với $50\%$ số điểm của bài thoả mãn: $N\le 1000$; $Q=1$.
• $30\%$ số test khác ứng với $30\%$ số điểm của bài thoả mãn: $N\le {10}^5$; $Q=1$.
• $20\%$ số 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ụ