{"code":"abc429_d","name":"On THDZ Conference","description":"Một cái hồ có chu vi $M$. Ta định nghĩa \"điểm $x$\" là vị trí cách một túp lều (ở mốc 0) một khoảng $x$ theo chiều kim đồng hồ ($0 \\le x < M$).\r\n\r\nCó $N$ người, người thứ $i$ đang đứng ở điểm $A_i$. Lưu ý: Nhiều người có thể đứng cùng một điểm.\r\n\r\nCho một số nguyên $C$ (với $1 \\le C \\le N$).\r\n\r\nVới mỗi $i$ từ $0$ đến $M-1$, ta định nghĩa giá trị $X_i$ như sau:\r\n1.  H bắt đầu ở điểm $(i + 0.5)$ và di chuyển theo chiều kim đồng hồ.\r\n2.  H tiếp tục di chuyển chừng nào tổng số người anh ấy đã gặp (tính từ lúc bắt đầu) vẫn còn **nhỏ hơn** $C$.\r\n3.  Anh ấy sẽ dừng lại ngay khi tổng số người đã gặp **lớn hơn hoặc bằng** $C$. Phép \"gặp\" một người tại điểm $y$ nghĩa là H đến chính xác điểm $y$.\r\n4.  $X_i$ là tổng số người Takahashi đã gặp *tính đến thời điểm anh ấy dừng lại*. (Lưu ý: Nếu anh ấy dừng tại một điểm có nhiều người, $X_i$ có thể lớn hơn $C$).\r\n\r\nYêu cầu: Tính tổng của tất cả các giá trị $X_i$, tức là $\\sum_{i=0}^{M-1} X_i$.\r\n\r\n## Input\r\n- Dòng đầu tiên chứa ba số nguyên $N, M, C$ ($1 \\le N \\le 5 \\times 10^5$, $1 \\le M \\le 10^{12}$, $1 \\le C \\le N$).\r\n- Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \\dots, A_N$ ($0 \\le A_i \\le M-1$), là vị trí của $N$ người.\r\n\r\n## Output\r\n- In ra một dòng duy nhất chứa tổng $\\sum_{i=0}^{M-1} X_i$.\r\n\r\n## Examples\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5 3 2\r\n        1 2 1 0 1\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        9\r\n        ```\r\n    ???+ info \"Explanation\"\r\n        Ta có $N=5$ người, chu vi $M=3$, và điều kiện dừng $C=2$.\r\n        Các vị trí người: ba người ở điểm 1, một người ở điểm 2, một người ở điểm 0.\r\n        Vì $M=3$, ta cần tính $X_0, X_1, X_2$.\r\n\r\n        * **Với $i=0$:** Bắt đầu ở 0.5. Di chuyển theo chiều kim đồng hồ.\r\n            * Gặp 3 người ở điểm 1. Tổng số người đã gặp = 3.\r\n            * Vì $3 \\ge C=2$, anh ấy dừng lại.\r\n            * $X_0 = 3$.\r\n        * **Với $i=1$:** Bắt đầu ở 1.5. Di chuyển theo chiều kim đồng hồ.\r\n            * Gặp 1 người ở điểm 2. Tổng số người đã gặp = 1.\r\n            * Vì $1 < C=2$, anh ấy đi tiếp.\r\n            * Gặp 1 người ở điểm 0 (sau khi qua mốc 2). Tổng số người đã gặp = $1 + 1 = 2$.\r\n            * Vì $2 \\ge C=2$, anh ấy dừng lại.\r\n            * $X_1 = 2$.\r\n        * **Với $i=2$:** Bắt đầu ở 2.5. Di chuyển theo chiều kim đồng hồ.\r\n            * Gặp 1 người ở điểm 0. Tổng số người đã gặp = 1.\r\n            * Vì $1 < C=2$, anh ấy đi tiếp.\r\n            * Gặp 3 người ở điểm 1. Tổng số người đã gặp = $1 + 3 = 4$.\r\n            * Vì $4 \\ge C=2$, anh ấy dừng lại.\r\n            * $X_2 = 4$.\r\n\r\n        Tổng cần tìm là $X_0 + X_1 + X_2 = 3 + 2 + 4 = 9$.\r\n\r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        1 1000000000000 1\r\n        1\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1000000000000\r\n        ```\r\n    ???+ info \"Explanation\"\r\n        Ta có $N=1$ người, chu vi $M=10^{12}$, và điều kiện dừng $C=1$. Có một người duy nhất ở điểm 1.\r\n        Ta cần tính $X_i$ cho $i = 0$ đến $M-1$.\r\n\r\n        Với mọi vị trí bắt đầu $i$ (từ $0$ đến $M-1$), Takahashi sẽ luôn di chuyển cho đến khi gặp người duy nhất ở điểm 1.\r\n        Khi gặp người đó, tổng số người đã gặp là 1. Vì $1 \\ge C=1$, anh ấy dừng lại.\r\n        Do đó, $X_i = 1$ với mọi $i$.\r\n\r\n        Tổng cần tìm là $\\sum_{i=0}^{M-1} X_i = \\underbrace{1 + 1 + \\dots + 1}_{M \\text{ lần}} = M = 10^{12}$.","points":100.0,"partial":false,"time_limit":1.0,"memory_limit":1024000,"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}}