問題一覧 > 通常問題

No.3812 Max Min Sigma Problem

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 13
作問者 : dyktr_06 / テスター : tyawanmusi sepa38
お気に入りにしたユーザー ProblemId : 14071 / 自分の提出
問題文最終更新日: 2026-09-21 05:19:54
yukicoder contest 524 (順位表) の他の問題:

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。

$1 \leq l \leq r \leq N$ を満たす整数 $l,r$ に対して、$f(l,r)$ を次のように定義します。

  • $A_l,A_{l+1},\ldots,A_r$ の最大値を $X$、最小値を $Y$ とすると、$f(l,r)=(X-Y)^2$

$\displaystyle \sum_{l=1}^{N}\sum_{r=l}^{N}f(l,r)$ を $998244353$ で割ったあまりを求めてください。

制約

  • $1 \leq N \leq 5 \times 10^5$
  • $1 \leq A_i \leq 10^9$
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

出力

答えを一行に出力してください。

サンプル

サンプル1
入力
3
1 2 3
出力
6

$\displaystyle \sum_{l=1}^{N}\sum_{r=l}^{N}f(l,r) = f(1, 1) + f(1, 2) + f(1, 3) + f(2, 2) + f(2, 3) + f(3, 3) = 0 + 1 + 4 + 0 + 1 + 0 = 6$ です。

サンプル2
入力
2
1 1000000000
出力
712559605

$998244353$ で割ったあまりを求めることに注意してください。

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