{"problem":{"name":"D. Two Melodies","description":{"content":"Alice is a beginner composer and now she is ready to create another masterpiece. And not even the single one but two at the same time! Alice has a sheet with _n_ notes written on it. She wants to tak","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF813D"},"statements":[{"statement_type":"Markdown","content":"Alice is a beginner composer and now she is ready to create another masterpiece. And not even the single one but two at the same time!\n\nAlice has a sheet with _n_ notes written on it. She wants to take two such non-empty non-intersecting subsequences that both of them form a _melody_ and sum of their lengths is maximal.\n\n_Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements._\n\nSubsequence forms a melody when each two adjacent notes either differs by _1_ or are congruent modulo _7_.\n\nYou should write a program which will calculate maximum sum of lengths of such two non-empty non-intersecting subsequences that both of them form a melody.\n\n## Input\n\nThe first line contains one integer number _n_ (2 ≤ _n_ ≤ 5000).\n\nThe second line contains _n_ integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 105) — notes written on a sheet.\n\n## Output\n\nPrint maximum sum of lengths of such two non-empty non-intersecting subsequences that both of them form a melody.\n\n[samples]\n\n## Note\n\nIn the first example subsequences \\[1, 2\\] and \\[4, 5\\] give length _4_ in total.\n\nIn the second example subsequences \\[62, 48, 49\\] and \\[60, 61\\] give length _5_ in total. If you choose subsequence \\[62, 61\\] in the first place then the second melody will have maximum length _2_, that gives the result of _4_, which is not maximal.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Alice 是一位初学者作曲家，现在她准备创作另一部杰作——而且不是一部，而是同时创作两部！\n\nAlice 有一张写有 #cf_span[n] 个音符的乐谱。她希望从中选出两个非空且互不相交的子序列，使得它们都构成一个 _旋律_，并且它们长度之和最大。\n\n_子序列是指通过删除某些元素而不改变剩余元素的顺序，从另一个序列中派生出的序列。_\n\n当一个子序列中每两个相邻的音符要么相差 _1_，要么对 _7_ 取模同余时，该子序列构成一个旋律。\n\n你需要编写一个程序，计算满足上述条件的两个非空、互不相交子序列的最大长度之和。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 5000]）。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]）——写在乐谱上的音符。\n\n请输出满足条件的两个子序列的最大长度之和。\n\n在第一个例子中，子序列 #cf_span[[1, 2]] 和 #cf_span[[4, 5]] 总长度为 _4_。\n\n在第二个例子中，子序列 #cf_span[[62, 48, 49]] 和 #cf_span[[60, 61]] 总长度为 _5_。如果你首先选择子序列 #cf_span[[62, 61]]，则第二个旋律的最大长度仅为 _2_，总和为 _4_，这不是最大值。\n\n## Input\n\n第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 5000]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]）——写在乐谱上的音符。\n\n## Output\n\n请输出满足条件的两个非空、互不相交子序列的最大长度之和。\n\n[samples]\n\n## Note\n\n在第一个例子中，子序列 #cf_span[[1, 2]] 和 #cf_span[[4, 5]] 总长度为 _4_。在第二个例子中，子序列 #cf_span[[62, 48, 49]] 和 #cf_span[[60, 61]] 总长度为 _5_。如果你首先选择子序列 #cf_span[[62, 61]]，则第二个旋律的最大长度仅为 _2_，总和为 _4_，这不是最大值。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of notes.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers representing the notes.  \n\nA subsequence $ S = (s_1, s_2, \\dots, s_k) $ forms a *melody* if for all $ i \\in \\{1, \\dots, k-1\\} $:  \n$$\n|s_i - s_{i+1}| = 1 \\quad \\text{or} \\quad s_i \\equiv s_{i+1} \\pmod{7}\n$$\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 5000 $  \n2. $ 1 \\leq a_i \\leq 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. Two subsequences must be non-empty, non-intersecting (no common index), and both must form a melody.  \n\n**Objective**  \nMaximize the sum of lengths of two such subsequences:  \n$$\n\\max_{\\substack{S_1, S_2 \\subseteq A \\\\ S_1 \\cap S_2 = \\emptyset \\\\ S_1, S_2 \\text{ are melodies} \\\\ S_1 \\neq \\emptyset, S_2 \\neq \\emptyset}} (|S_1| + |S_2|)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF813D","tags":["dp","flows"],"sample_group":[["4\n1 2 4 5","4"],["6\n62 22 60 61 48 49","5"]],"created_at":"2026-03-03 11:00:39"}}