{"code":"macumamoi","name":"Ma cũ ma mới","description":"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?.\r\n\r\n

Input

\r\n\r\n- Dòng thứ nhất là số nguyên $n\\ (1 \\le n \\le 10^5)$\r\n- 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)$\r\n\r\n

Output

\r\n\r\n- 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)$\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 4\r\n 3 2 4 1\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 7\r\n ```\r\n\r\n ??? warning \"Note\"\r\n - Con ma 2 đưa cho con ma 3: 1 đồng tiền vàng. \r\n - Con ma 4: không đưa. \r\n - Con ma 1 đưa cho con ma 3 (2 đồng), con ma 2 (1 đồng), con ma 4 (3 đồng).\r\n - Tổng cộng 7 đồng.","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}