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à a1, a2,..., an. 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
- Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 105)
- Dòng thứ hai là n số nguyên a1, a2, ..., an, mỗi số cách nhau một khoảng trắng (1 ≤ ai ≤ 109)
Kết quả
- 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 109)
input
4
3 2 4 1
output
7
Giải thích
1) Con ma 2 đưa cho con ma 3: 1 đồng tiền vàng.
2) Con ma 4: không đưa.
3) Con ma 1 đưa cho con ma 3 (2 đồng), con ma 2 (1 đồng), con ma 4 (3 đồng).
Tổng cộng 7 đồng.
Nguồn: NTU