{"problem":{"name":"C. Boxes Packing","description":{"content":"Mishka has got _n_ empty boxes. For every _i_ (1 ≤ _i_ ≤ _n_), _i_\\-th box is a cube with side length _a__i_. Mishka can put a box _i_ into another box _j_ if the following conditions are met: *   _","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF903C"},"statements":[{"statement_type":"Markdown","content":"Mishka has got _n_ empty boxes. For every _i_ (1 ≤ _i_ ≤ _n_), _i_\\-th box is a cube with side length _a__i_.\n\nMishka can put a box _i_ into another box _j_ if the following conditions are met:\n\n*   _i_\\-th box is not put into another box;\n*   _j_\\-th box doesn't contain any other boxes;\n*   box _i_ is smaller than box _j_ (_a__i_ < _a__j_).\n\nMishka can put boxes into each other an arbitrary number of times. He wants to minimize the number of _visible_ boxes. A box is called _visible_ iff it is not put into some another box.\n\nHelp Mishka to determine the minimum possible number of _visible_ boxes!\n\n## Input\n\nThe first line contains one integer _n_ (1 ≤ _n_ ≤ 5000) — the number of boxes Mishka has got.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109), where _a__i_ is the side length of _i_\\-th box.\n\n## Output\n\nPrint the minimum possible number of _visible_ boxes.\n\n[samples]\n\n## Note\n\nIn the first example it is possible to put box 1 into box 2, and 2 into 3.\n\nIn the second example Mishka can put box 2 into box 3, and box 4 into box 1.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Mishka 有 #cf_span[n] 个空盒子。对于每个 #cf_span[i]（#cf_span[1 ≤ i ≤ n]），第 #cf_span[i] 个盒子是一个边长为 #cf_span[ai] 的立方体。\n\nMishka 可以将盒子 #cf_span[i] 放入盒子 #cf_span[j] 中，当且仅当满足以下条件：\n\nMishka 可以任意多次将盒子嵌套放入其他盒子中。他希望最小化 _可见_ 盒子的数量。一个盒子被称为 _可见_，当且仅当它没有被放入任何其他盒子中。\n\n请帮助 Mishka 确定 _可见_ 盒子的最小可能数量！\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5000]）——Mishka 拥有的盒子数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]），其中 #cf_span[ai] 是第 #cf_span[i] 个盒子的边长。\n\n请输出 _可见_ 盒子的最小可能数量。\n\n在第一个例子中，可以将盒子 #cf_span[1] 放入盒子 #cf_span[2]，再将 #cf_span[2] 放入 #cf_span[3]。\n\n在第二个例子中，Mishka 可以将盒子 #cf_span[2] 放入盒子 #cf_span[3]，并将盒子 #cf_span[4] 放入盒子 #cf_span[1]。\n\n## Input\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5000]）——Mishka 拥有的盒子数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]），其中 #cf_span[ai] 是第 #cf_span[i] 个盒子的边长。\n\n## Output\n\n请输出 _可见_ 盒子的最小可能数量。\n\n[samples]\n\n## Note\n\n在第一个例子中，可以将盒子 #cf_span[1] 放入盒子 #cf_span[2]，再将 #cf_span[2] 放入 #cf_span[3]。在第二个例子中，Mishka 可以将盒子 #cf_span[2] 放入盒子 #cf_span[3]，并将盒子 #cf_span[4] 放入盒子 #cf_span[1]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of boxes.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers representing the side lengths of the boxes.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 5000 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nFind the minimum number of visible boxes, where a box $ a_i $ can be placed inside box $ a_j $ if and only if $ a_i < a_j $.  \nBoxes can be nested recursively. The goal is to minimize the number of outermost (visible) boxes.\n\nThis is equivalent to finding the size of the **minimum number of decreasing subsequences** that partition the multiset $ A $, which by Dilworth’s theorem equals the size of the **longest non-decreasing subsequence** of $ A $.\n\nThus, the minimum number of visible boxes is equal to the length of the **longest non-decreasing subsequence** of $ A $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF903C","tags":["greedy"],"sample_group":[["3\n1 2 3","1"],["4\n4 2 4 3","2"]],"created_at":"2026-03-03 11:00:39"}}