{"problem":{"name":"A. Ambiguous Dates","description":{"content":"There are two popular formats for representing a date: _day/month/year_ or _month/day/year_. For example, today can be represented as 15/8/2017 or 8/15/2017. Sometimes (like on today), using one way ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10152A"},"statements":[{"statement_type":"Markdown","content":"There are two popular formats for representing a date: _day/month/year_ or _month/day/year_. For example, today can be represented as 15/8/2017 or 8/15/2017.\n\nSometimes (like on today), using one way or another should pose no confusion — it is immediately understood that the date is the 15th of August. On other days, however, the two representations may be interpreted as two different valid dates. For example, the 7th of August may be misinterpreted as the 8th of July, since both can be represented as 7/8/2017 (or 8/7/2017).\n\nWe say a date (D, M, Y) is ambiguous if D/M/Y and M/D/Y, when both interpreted in the _day/month/year_ format, are different valid dates. For example, (7, 8, 2017) and (8, 7, 2017) are ambiguous, while (15, 8, 2017) and (10, 10, 2017) are not.\n\nThe total number of ambiguous dates in the Gregorian calendar system on any given year is equal to 12 × 11 = 132.\n\nNow, suppose that in a hypothetical calendar system, there are M months, where the i-th month has D[i] days, numbered from 1 to D[i]. Assume that there are no leap years.\n\nYou are to carry out a calendar reform, by shuffling the array D[], and your target is to minimize the total number of ambiguous dates in a calendar year. Specifically, you want to find a permutation p[1, p[2], ..., p[M]] of integers 1, 2, ..., M, such that the new calendar system, where the i-th month has D[p[i]] days, has the minimal number of ambiguous dates. Output that minimal number.\n\nThe first line of input consists of a single integer M, the number of months in the hypothetical calendar system.\n\nThe second line of input consists of M integers D[1, D[2], ..., D[M]], the original number of days in the i-th month.\n\nFor all test cases, 1 ≤ M ≤ 105, 1 ≤ D[i ≤ 105].\n\nOutput a single integer, the minimal number of ambiguous dates after the calendar reform.\n\n## Input\n\nThe first line of input consists of a single integer M, the number of months in the hypothetical calendar system.The second line of input consists of M integers D[1, D[2], ..., D[M]], the original number of days in the i-th month.For all test cases, 1 ≤ M ≤ 105, 1 ≤ D[i ≤ 105].\n\n## Output\n\nOutput a single integer, the minimal number of ambiguous dates after the calendar reform.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ M \\in \\mathbb{Z}^+ $ be the number of months.  \nLet $ D = (d_1, d_2, \\dots, d_M) $ be a sequence of positive integers, where $ d_i $ is the number of days in month $ i $.  \nLet $ p $ be a permutation of $ \\{1, 2, \\dots, M\\} $, defining a reordered calendar where month $ i $ has $ d_{p[i]} $ days.  \n\n**Ambiguous Date Definition**  \nA date $ (a, b, Y) $ is *ambiguous* if:  \n- $ 1 \\leq a \\leq d_{p[b]} $,  \n- $ 1 \\leq b \\leq d_{p[a]} $,  \n- $ a \\neq b $,  \nand both $ (a, b, Y) $ and $ (b, a, Y) $ are valid dates under the reordered calendar.  \n\n**Objective**  \nMinimize the total number of ambiguous dates over all permutations $ p $:  \n$$\n\\min_{p \\in S_M} \\sum_{\\substack{1 \\leq a, b \\leq M \\\\ a \\neq b}} \\mathbf{1}_{a \\leq d_{p[b]} \\text{ and } b \\leq d_{p[a]}}\n$$\n\n**Constraints**  \n- $ 1 \\leq M \\leq 10^5 $  \n- $ 1 \\leq d_i \\leq 10^5 $ for all $ i \\in \\{1, \\dots, M\\} $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10152A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}