Có \(n\) con ma lần lượt gia nhập nghĩa trang theo thứ tự là \(1, 2, 3,..., n\). Chỉ số sức mạnh của các con ma tương ứng là \(a_1, a_2,..., a_n\). Khi một con ma mới gia nhập nghĩa trang thì nó sẽ bị các con ma cũ bắt nạt. Giả sử con ma mới có chỉ số sức mạnh là \(M\) và con ma cũ có chỉ số sức mạnh là \(C\), nếu \(M < C\) thì con ma mới phải nộp cho con ma cũ \(C - M\) đồng tiền vàng. Nếu \(M \ge C\) thì thôi. Bạn hãy tính thử xem sau khi đủ \(n\) con ma gia nhập nghĩa trang thì các con ma phải đưa lẫn nhau tổng cộng bao nhiêu đồng tiền vàng?.

Input

• Dòng thứ nhất là số nguyên \(n\ (1 \le n \le 10^5)\)
• Dòng thứ hai là \(n\) số nguyên \(a_1, a_2, ..., a_n\), mỗi số cách nhau một khoảng trắng \((1 \le a_i \le 10^9)\)

Output

• Là số nguyên xác định tổng cộng số đồng tiền vàng các con ma đưa lẫn nhau. Chỉ cần in ra \(9\) chữ số cuối \((\mod\ 10^9)\)

Example

4
3 2 4 1

7