{"problem":{"name":"E. Vladik and cards","description":{"content":"Vladik was bored on his way home and decided to play the following game. He took _n_ cards and put them in a row in front of himself. Every card has a positive integer number not exceeding 8 written o","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF743E"},"statements":[{"statement_type":"Markdown","content":"Vladik was bored on his way home and decided to play the following game. He took _n_ cards and put them in a row in front of himself. Every card has a positive integer number not exceeding 8 written on it. He decided to find the longest subsequence of cards which satisfies the following conditions:\n\n*   the number of occurrences of each number from 1 to 8 in the subsequence doesn't differ by more then 1 from the number of occurrences of any other number. Formally, if there are _c__k_ cards with number _k_ on them in the subsequence, than for all pairs of integers the condition |_c__i_ - _c__j_| ≤ 1 must hold.\n*   if there is at least one card with number _x_ on it in the subsequence, then all cards with number _x_ in this subsequence must form a continuous segment in it (**but not necessarily a continuous segment in the original sequence**). For example, the subsequence \\[1, 1, 2, 2\\] satisfies this condition while the subsequence \\[1, 2, 2, 1\\] doesn't. Note that \\[1, 1, 2, 2\\] doesn't satisfy the first condition.\n\nPlease help Vladik to find the length of the longest subsequence that satisfies both conditions.\n\n## Input\n\nThe first line contains single integer _n_ (1 ≤ _n_ ≤ 1000) — the number of cards in Vladik's sequence.\n\nThe second line contains the sequence of _n_ positive integers not exceeding 8 — the description of Vladik's sequence.\n\n## Output\n\nPrint single integer — the length of the longest subsequence of Vladik's sequence that satisfies both conditions.\n\n[samples]\n\n## Note\n\nIn the first sample all the numbers written on the cards are equal, so you can't take more than one card, otherwise you'll violate the first condition.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Vladik 在回家的路上感到无聊，决定玩以下游戏。他拿了 #cf_span[n] 张卡片，并将它们排成一排放在自己面前。每张卡片上写有一个不超过 #cf_span[8] 的正整数。他希望找到一个最长的子序列，满足以下条件：\n\n请帮助 Vladik 找出满足两个条件的最长子序列的长度。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1000]) —— Vladik 序列中卡片的数量。\n\n第二行包含 #cf_span[n] 个不超过 #cf_span[8] 的正整数序列 —— Vladik 序列的描述。\n\n请输出一个整数 —— 满足两个条件的 Vladik 序列的最长子序列的长度。\n\n在第一个样例中，所有卡片上的数字都相等，因此你不能取超过一张卡片，否则将违反第一个条件。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1000]) —— Vladik 序列中卡片的数量。第二行包含 #cf_span[n] 个不超过 #cf_span[8] 的正整数序列 —— Vladik 序列的描述。\n\n## Output\n\n请输出一个整数 —— 满足两个条件的 Vladik 序列的最长子序列的长度。\n\n[samples]\n\n## Note\n\n在第一个样例中，所有卡片上的数字都相等，因此你不能取超过一张卡片，否则将违反第一个条件。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\nLet $ a = (a_1, a_2, \\dots, a_n) $ be a sequence of $ n $ positive integers, where $ 1 \\leq n \\leq 1000 $ and $ 1 \\leq a_i \\leq 8 $ for all $ i $.\n\nLet $ S $ be a subsequence of $ a $, i.e., a sequence $ S = (a_{i_1}, a_{i_2}, \\dots, a_{i_k}) $ with $ 1 \\leq i_1 < i_2 < \\dots < i_k \\leq n $.\n\n**Constraints:**\n\n1. All elements in $ S $ are distinct.\n2. For every pair of consecutive elements in $ S $, say $ (x, y) $, if $ x $ appears at position $ i $ and $ y $ at position $ j $ in the original sequence $ a $, then $ i < j $ (i.e., $ S $ is a subsequence in order).\n\n**Objective:**\n\nMaximize the length $ |S| $ of such a subsequence $ S $.\n\n---\n\n**Formal Statement:**\n\nFind the maximum length $ k $ of a subsequence $ S = (s_1, s_2, \\dots, s_k) $ of $ a $ such that:\n\n- $ s_i \\ne s_j $ for all $ i \\ne j $, and  \n- $ s_1, s_2, \\dots, s_k $ appear in $ a $ in increasing order of indices.\n\n---\n\n**Note:** Since values are bounded by 8, the maximum possible length of such a subsequence is at most 8.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF743E","tags":["binary search","bitmasks","brute force","dp"],"sample_group":[["3\n1 1 1","1"],["8\n8 7 6 5 4 3 2 1","8"],["24\n1 8 1 2 8 2 3 8 3 4 8 4 5 8 5 6 8 6 7 8 7 8 8 8","17"]],"created_at":"2026-03-03 11:00:39"}}