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₁, a₂,..., 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 ≥ 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?.

Dữ liệu nhập:

- Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 10⁵)

- Dòng thứ hai là n số nguyên a₁, a₂, ..., a_n, mỗi số cách nhau một khoảng trắng (1 ≤ a_i ≤ 10⁹)  

Dữ liệu xuất:

- 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⁹)