English · Original
Chinese · Translation
Formal · Original
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 take two such non-empty non-intersecting subsequences that both of them form a _melody_ and sum of their lengths is maximal.
_Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements._
Subsequence forms a melody when each two adjacent notes either differs by _1_ or are congruent modulo _7_.
You 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.
## Input
The first line contains one integer number _n_ (2 ≤ _n_ ≤ 5000).
The second line contains _n_ integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 105) — notes written on a sheet.
## Output
Print maximum sum of lengths of such two non-empty non-intersecting subsequences that both of them form a melody.
[samples]
## Note
In the first example subsequences \[1, 2\] and \[4, 5\] give length _4_ in total.
In 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.
Alice 是一位初学者作曲家，现在她准备创作另一部杰作——而且不是一部，而是同时创作两部！
Alice 有一张写有 #cf_span[n] 个音符的乐谱。她希望从中选出两个非空且互不相交的子序列，使得它们都构成一个 _旋律_，并且它们长度之和最大。
_子序列是指通过删除某些元素而不改变剩余元素的顺序，从另一个序列中派生出的序列。_
当一个子序列中每两个相邻的音符要么相差 _1_，要么对 _7_ 取模同余时，该子序列构成一个旋律。
你需要编写一个程序，计算满足上述条件的两个非空、互不相交子序列的最大长度之和。
第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 5000]）。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]）——写在乐谱上的音符。
请输出满足条件的两个子序列的最大长度之和。
在第一个例子中，子序列 #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_，这不是最大值。
## Input
第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 5000]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]）——写在乐谱上的音符。
## Output
请输出满足条件的两个非空、互不相交子序列的最大长度之和。
[samples]
## Note
在第一个例子中，子序列 #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_，这不是最大值。
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of notes.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers representing the notes.
A subsequence $ S = (s_1, s_2, \dots, s_k) $ forms a *melody* if for all $ i \in \{1, \dots, k-1\} $:
$$
|s_i - s_{i+1}| = 1 \quad \text{or} \quad s_i \equiv s_{i+1} \pmod{7}
$$
**Constraints**
1. $ 2 \leq n \leq 5000 $
2. $ 1 \leq a_i \leq 10^5 $ for all $ i \in \{1, \dots, n\} $
3. Two subsequences must be non-empty, non-intersecting (no common index), and both must form a melody.
**Objective**
Maximize the sum of lengths of two such subsequences:
$$
\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|)
$$
API Response (JSON)
{
"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 tak...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Alice 是一位初学者作曲家，现在她准备创作另一部杰作——而且不是一部，而是同时创作两部！\n\nAlice 有一张写有 #cf_span[n] 个音符的乐谱。她希望从中选出两个非空且互不相交的子序列，使得它们都构成一个 _旋律_，并且它们长度之和最大。\n\n_子序列是指通过删除某些元素而不改变剩余元素的顺序，从另一个序列中派生出的序列。_\n\n当一个子序列中每两个相邻的音符要么相差 _1_，要么对 _...",
"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) ...",
"is_translate": false,
"language": "Formal"
}
]
}