問題文問題文の言語日本語한국어 English 日本語 简体中文한국어English日本語简体中文2N2N2N 人が 111 番から 2N2N2N 番まで順に一列に並んでいる。1≤i<2N1\leq i<2N1≤i<2N に対し、iii 番目と i+1i+1i+1 番目の間に高さ HiH_iHi の塀がある。二人 a<ba<ba<b を組にする費用は max(Ha,Ha+1,…,Hb−1)\max(H_a,H_{a+1},\ldots,H_{b-1})max(Ha,Ha+1,…,H である。各人がちょうど一つの組に含まれるように NNN 組を作るとき、費用の総和の最小値を求めよ。組を表す区間は重なったり交差したりしてもよい。入力入力は以下の形式で与えられる。NNN H1 H2 ⋯ H2N−1H_1\ H_2\ \cdots\ H_{2N-1}H1 H2 ⋯ 出力費用の総和の最小値を出力せよ。制約 1≤N≤200 0001 \leq N \leq 200\ 0001≤N≤200 000. 1≤Hi≤1091 \leq H_i \leq 10^91≤Hi (). サブタスク#得点制約120N≤8N \leq 8N≤8.280追加の制約はない。サンプル例 1入力例コピー2 100 1 100出力例コピー101例 2入力例コピー1 7出力例コピー7例 3入力例コピー3 4 4 4 4 4出力例コピー12
