問題一覧 > 通常問題

No.1294 マウンテン数列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 36
作問者 : 沙耶花沙耶花 / テスター : tko919tko919
6 ProblemId : 4473 / 出題時の順位表
問題文最終更新日: 2020-10-04 20:56:50

問題文

ある単調増加な数列$X$と単調減少な数列$Y$をこの順に連結することで得られる数列をマウンテン数列と呼ぶことにします.

また, 長さ2以上のマウンテン数列$\{x_1,x_2,...,x_n\}$に対し,
$|x_1 - x_2|,|x_2-x_3|,...,|x_{n-1}-x_n|$のうち最大の値をその数列の危険度と呼ぶことにします.
例えば, 数列$\{3, 7, 9, 4\}$や$\{1, 2,4\}$はどちらもマウンテン数列であり, 危険度は順に5, 2です.

どの要素も相異なる正整数列$\{A_1,A_2,...,A_N\}$が与えられます.
これを並び替えて得られるマウンテン数列すべてに対しその危険度を求め,
総和を$\bmod 998244353$で出力してください.

入力

$N$
$A_1\ A_2\ ...\ A_N$

  • $2 \le N \le 2500$
  • $1 \le A_1 < A_2 < ... < A_N \le 2500$
  • 入力はすべて整数

出力

答えを出力してください.
最後に改行してください.

サンプル

サンプル1
入力
3
1 2 4
出力
10

並べ替えて得られるマウンテン数列は$\{1,2,4\},\{1,4,2\},\{2,4,1\},\{4,2,1\}$の4通りです.
これらの危険度は順に2,3,3,2なので, この合計である10を出力します.

サンプル2
入力
4
3 4 7 9
出力
38

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