Lợi nhuận tối đa một giao dịch

Cho dãy giá cổ phiếu $p_1,p_2,\dots ,p_n$ trong $n$ ngày liên tiếp. Bạn được phép thực hiện đúng một giao dịch: chọn ngày $i$ để mua với giá $p_i$, sau đó chọn ngày $j$ để bán với giá $p_j$, trong đó $1\le i\le j\le n$. Lợi nhuận thu được là $p_j-p_i$.

Hãy tìm lợi nhuận lớn nhất có thể đạt được. Nếu mọi cách chọn đều cho lợi nhuận âm hoặc bằng $0$, bạn có quyền không giao dịch và lợi nhuận khi đó là $0$.

Có $q$ trường hợp test độc lập (multitest).

Dữ liệu vào

• Dòng đầu chứa số nguyên $q$ — số trường hợp test.
• Với mỗi trường hợp test:
  • Dòng đầu chứa số nguyên $n$.
  • Dòng tiếp theo chứa $n$ số nguyên $p_1,p_2,\dots ,p_n$ cách nhau bởi dấu cách.

Dữ liệu ra

In $q$ dòng, mỗi dòng là đáp án của trường hợp test tương ứng.

Ràng buộc

• $1\le q\le 10$
• $1\le n\le 2·{10}^5$
• $1\le p_i\le {10}^9$
• Tổng $n$ qua tất cả các trường hợp test không vượt quá ${10}^6$.

Ví dụ

Ghi chú

Đáp án có thể vừa khít $32$-bit (giá tối đa ${10}^9$), nhưng nên dùng kiểu nguyên đủ rộng và cẩn thận khi sử dụng kiểu không dấu.