{"code":"chiakem","name":"Chia kem cho những đứa trẻ","description":"Sau khi xem xong MV \"**Ice Cream**\" của **Blackpink**, [user:bin9638] và [user:algorit] liền đặt ngay vé máy bay sang Hàn Quốc để có thể ăn kem tại quán và nói chuyện với các idol của mình. Lúc [user:bin9638] và [user:algorit] tới quán kem \"**Blackpink**\" thì đúng lúc quán kem này đang có chương trình phát kem cho các em nhỏ. Cụ thể, có $n$ đứa trẻ lần lượt có độ tuổi là $A_1 , A_2 , ... , A_n$ đang đứng trước quán chờ nhận kem, đứa trẻ thứ $i$ có độ tuổi là $A_i$ . Chương trình phát kem của **Blackpink** cũng rất đặc biệt, mỗi đứa trẻ phải có ít nhất $1$ que kem , khi có $2$ đứa trẻ đứng gần nhau , đứa trẻ **lớn hơn** sẽ được phát **nhiều** kem hơn, nếu $2$ đứa trẻ cùng tuổi đứng cạnh nhau thì phát tùy ý. Tuy nhiên vì còn phải đi phát kem ở nhiều nơi nữa nên **Blackpink** muốn số kem được phát là **tối thiểu**.\r\n\r\n**Lisa**, quản lí của quán kem này biết [user:bin9638] và [user:algorit] là những người rất thông minh nên muốn nhờ họ tính giúp số kem tối thiểu cần phát. Nếu tính được thì [user:bin9638] và [user:algorit] sẽ được tặng $2$ que kem, hơn nữa họ còn sẽ được chụp ảnh chung và có được chữ kí của **Blackpink** nữa đấy. Hãy giúp họ nhé !\r\n\r\n#### Yêu cầu:\r\n- Hãy tìm số lượng kem tối thiểu đề chia cho $n$ đứa trẻ.\r\n\r\n#### Input:\r\n - Dòng đầu tiên gồm $1$ số nguyên dương $n$ . $(n \\le 10^6)$\r\n - Dòng thứ $2$ là dãy số $A_1 , A_2 , ... , A_n$ là độ tuổi của nhứng đứa trẻ . $(A_i \\le 10^9)$\r\n\r\n\r\n#### Output:\r\n - Dòng đầu tiên gồm một số nguyên dương duy nhất là số lượng kem tối thiểu.\r\n - Dòng thứ $2$ là dãy $C_i$ tương ứng với số kem phát cho đứa trẻ thứ $i$.\r\n\r\n#### Scoring:\r\n - Subtask $1$ ($40\\%$ số điểm): $n \\le 10^3$\r\n - Subtask $2$ ($60\\%$ số điểm): không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5\r\n        1 2 1000000000 2 1 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        9\r\n        1 2 3 2 1 \r\n        ```\r\n\r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3\r\n        1 2 2 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        4\r\n        1 2 1 \r\n        ```","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"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}}