No.831 都市めぐり

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 65
作問者 : Shuz*Shuz* / テスター : tatyamtatyam
1 ProblemId : 2444 / 出題時の順位表

問題文

ふーりぇ君はShuz国の都市めぐりをしています。
Shuz国には、 $N$ 個の都市があり、それぞれ $1,\ 2,\ 3,\ ...,\ N$ の番号がつけられています。
すべての $2$ 都市間は高速道路で結ばれており、$i \neq j$ のとき、都市 $i,\ j$ 間を移動するのに片道 $(i \times j)$ 円の基本料金がかかります。
また、都市 $i$ から都市 $j$ へ移動するのに、 $i \lt j$ のときは $(j-i)$ 円の追加料金が発生し、 $i \gt j$ のときは $(i-j)$ 円割引されます。
つまり、 $i \neq j$ のとき、都市 $i$ から都市 $j$ へ移動するのに合計 $(i \times j)+(j-i)$ 円かかります。
ふーりぇ君は、好きな都市から始めて、高速道路を使ってShuz国の都市を一周したいです。
ふーりぇ君が、 $N$ 個すべての都市を $1$ 回ずつめぐり最初にいた都市へ戻ってくるために最低限必要な料金を求めて下さい。

制約

  • $1 \le N \le 2 \times 10^6$
  • 入力はすべて整数

入力

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

$N$

出力

ふーりぇ君がすべての都市を $1$ 回ずつめぐるために最低限必要な料金を出力せよ。

サンプル

サンプル1
入力
3
出力
11

例えば、最も料金の少ない順路の一つは、
都市 $2$ から都市 $1$ まで $1$ 円
都市 $1$ から都市 $3$ まで $5$ 円
都市 $3$ から都市 $2$ まで $5$ 円
合計 $11$ 円
なので、合計料金である $11$ を出力します。

サンプル2
入力
1
出力
0

$1$ つしか都市がない場合は都市をめぐる必要がないので、料金はかかりません。

サンプル3
入力
200
出力
1353499

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。