問題一覧 > 通常問題

No.1368 サイクルの中に眠る門松列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 108
作問者 : 👑 mai 👑mai 👑 / テスター : ir_1st_vilir_1st_vil
1 ProblemId : 4270 / 出題時の順位表
問題文最終更新日: 2021-01-07 02:19:43

定義

3つの要素から成る数列$v = (a_1,a_2,a_3)$が次の条件を満たす時、$v$は門松列であると言い伝えられています。

  1. $a_1,a_2,a_3$は全て異なる
  2. 3つの要素のうち$a_2$が最も大きい、あるいは最も小さい

問題文

$N$ 個の整数 $A_1,\ldots,A_N$ が時計回りに円状に並んでいます。
円の中心から見て $A_i$ の右隣は $A_{i+1}$ です。また、$A_N$ の右隣は $A_1$ です。

ある連続する3要素を元の順序で並べた列が門松列であるならば、それらをグループにすることができます。
各要素が属することができるのは高々1つのグループであり、2つ以上のグループに属することはできません。

ここで、グループの評価値を3要素のうち円の中心から見て左端の整数の値とします。
適切にグループを作成したときのグループの評価値の総和の最大値を出力してください。
なお、グループを作成しない場合、グループの評価値の総和は $0$ とします。

入力

1つの入力に複数のテストケースが含まれる場合があります。

1行目にテストケースの個数 $T$ が与えられます。
続く各2行ごとに、各テストケースが与えられます。

$T$
$N_1$
$A_{1,1}\ \ldots\ A_{1,N_1}$
$\vdots$
$N_T$
$A_{T,1}\ \ldots\ A_{T,N_T}$

$1 \le T \le 2\times 10^4$
$3 \le N_j \le 2\times 10^5$
$1\le A_{j, i} \le 2\times 10^5$
$\sum_{j\in 1\ldots T}N_j \le 2\times 10^5$

入力に含まれる値はすべて整数である。

出力

各テストケースにおけるグループの評価値の総和の最大値を改行区切りで出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
3
1 2 3
6
2 1 99 2 3 1
4
1 1 1 1
出力
3
99
0

1つ目のテストケースでは、[3 1 2] とグルーピングすることで最大値 $3$ を得ることができます。
[2 3 1] とグルーピングすることもできますが、この場合の評価値の総和は $2$ であるため最適解ではありません。

2つ目のテストケースでは、[99 2 3] とグルーピングすることで最大値 $99$ を得ることができます。[1 2 1]は門松列では無いので、グルーピングできません。
また、[2 1 99] [2 3 1] とグルーピングすることもできます。この場合グループの数は多いですが、評価値の総和は $2+2=4$ であるため最適解ではありません。

3つ目のテストケースでは、1つもグループを作成できません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。