AT_s8pc_6_g Medals

[problemUrl]: https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_g 時は 2212 年。競技プログラミングというスポーツの規模も広がり、国際情報オリンピックが世界で一躍有名になりました！ さて、この年の国際情報オリンピック (IOI) には $ N $ 人の参加者がいます。競技は $ 2 $ 日間に渡って行われます。 - $ 1 $ 日目：筆記試験を行う。選手 $ i $ は $ A_i $ 点を獲得した。**筆記試験では同点はいなかった。** - $ 2 $ 日目：実技試験を行う。実技試験では、試験の結果によって $ 1 $ 点から $ N $ 点までの点数が $ 1 $ 人ずつに付けられる。最も良い技を見せた選手には $ N $ 点、$ 2 $ 番目に良い技を見せた選手には $ N\ -\ 1 $ 点、… 最も悪い技を見せた選手には $ 1 $ 点が付けられる。 あなたは $ 1 $ 日目の競技の得点を知っています。しかし、$ 2 $ 日目の競技の得点は誰の得点に関しても知りません。 さて、選手の **順位** は、以下のようにして決まります。 - 基本的に、より合計点が高い選手がより高い順位になる。(ただし一番高い順位は $ 1 $ であり、一番低い順位は $ N $ である。) - ただし同点が存在する場合、同点内での順位は抽選によってランダムに決まる。 $ 1 $ 位を取った人が金メダル、$ 2 $ 位を取った人が銀メダル、$ 3 $ 位を取った人が銅メダルを獲得します。 また、あなたはメダリストの情報について、$ 1 $ つだけ知っています。これは、$ P $ ($ P $ は $ 1 $ または $ 2 $) によって表され： - $ P\ =\ 1 $ のとき、**メダリストのみで** $ 1 $ 日目の点数を高い順に並び替えると、(金, 銀, 銅) となる。 - $ P\ =\ 2 $ のとき、**メダリストのみで** $ 1 $ 日目の点数を高い順に並び替えると、(金, 銅, 銀) となる。 そのとき、(金メダリスト, 銀メダリスト, 銅メダリスト) の組は何通りあるでしょうか？

入力は以下の形式で標準入力から与えられる. > $ N $ $ P $ $ A_1 $ $ A_2 $ $ A_3 $ ... $ A_N $

(金, 銀, 銅) の組としてあり得る通り数を $ 1 $ 行に出力してください。

### 制約 - $ N $ は $ 5 $ 以上 $ 1\ 000\ 000 $ 以下の整数 - $ P $ は $ 1 $ または $ 2 $ - $ A_i $ は $ 1 $ 以上 $ 1\ 000\ 000\ 000 $ 以下の整数 - $ A_i $ は全て相異なる ### 小課題・得点 この問題には $ 2 $ つの小課題がある。 1. (600 点)：$ P\ =\ 1 $ 2. (600 点)：$ P\ =\ 2 $ それぞれの小課題は、次のような $ 12 $ 個の部分点データセットからなる。部分点の条件を満たすテストケースにすべて正解した場合に、「この部分点データセットに正解した」とみなされる。 1. (50 点)：$ 5\ \leq\ N\ \leq\ 7 $ 2. (50 点)：$ 5\ \leq\ N\ \leq\ 15 $ 3. (50 点)：$ 5\ \leq\ N\ \leq\ 30 $ 4. (50 点)：$ 5\ \leq\ N\ \leq\ 70 $ 5. (50 点)：$ 5\ \leq\ N\ \leq\ 200 $ 6. (50 点)：$ 5\ \leq\ N\ \leq\ 600 $ 7. (50 点)：$ 5\ \leq\ N\ \leq\ 2\ 000 $ 8. (50 点)：$ 5\ \leq\ N\ \leq\ 8\ 000 $ 9. (50 点)：$ 5\ \leq\ N\ \leq\ 50\ 000 $ 10. (50 点)：$ 5\ \leq\ N\ \leq\ 200\ 000 $ 11. (50 点)：$ 5\ \leq\ N\ \leq\ 500\ 000 $ 12. (50 点)：$ 5\ \leq\ N\ \leq\ 1\ 000\ 000 $ 提出したソースコードの得点は、$ 2 $ つの小課題の「正解した部分点データセットの点数の合計」を足し算した値です。 ### Sample Explanation 1 次の $ 4 $ つの可能性があります。金メダリストが選手 $ i $、銀メダリストが選手 $ j $、銅メダリストが選手 $ k $ のときを $ (i,\ j,\ k) $ で表します。 - $ (5,\ 3,\ 1) $ のケース：$ 2 $ 日目の点数が選手 $ 1 $ から順に $ 3,\ 4,\ 2,\ 1,\ 5 $ のとき、合計点は $ 6,\ 5,\ 8,\ 5,\ 13 $ となり、条件を満たす。 - $ (5,\ 3,\ 2) $ のケース：$ 2 $ 日目の点数が選手 $ 1 $ から順に $ 2,\ 4,\ 3,\ 1,\ 5 $ のとき、合計点は $ 5,\ 5,\ 9,\ 5,\ 13 $ となり、抽選の結果によっては条件を満たす。 - $ (5,\ 3,\ 4) $ のケース：$ 2 $ 日目の点数が選手 $ 1 $ から順に $ 1,\ 2,\ 3,\ 4,\ 5 $ のとき、合計点は $ 4,\ 3,\ 9,\ 8,\ 13 $ となり、条件を満たす。 - $ (5,\ 4,\ 1) $ のケース：$ 2 $ 日目の点数が選手 $ 1 $ から順に $ 4,\ 2,\ 1,\ 3,\ 5 $ のとき、合計点は $ 7,\ 3,\ 7,\ 7,\ 13 $ となり、抽選の結果によっては条件を満たす。 ### Sample Explanation 2 次の $ 3 $ つの可能性があります。金メダリストが選手 $ i $、銀メダリストが選手 $ j $、銅メダリストが選手 $ k $ のときを $ (i,\ j,\ k) $ で表します。 - $ (4,\ 2,\ 1) $ のケース：$ 2 $ 日目の点数が選手 $ 1 $ から順に $ 1,\ 5,\ 3,\ 4,\ 2 $ のとき、合計点は $ 7,\ 9,\ 4,\ 11,\ 4 $ となり、条件を満たす。 - $ (4,\ 5,\ 1) $ のケース：$ 2 $ 日目の点数が選手 $ 1 $ から順に $ 1,\ 2,\ 3,\ 4,\ 5 $ のとき、合計点は $ 7,\ 6,\ 4,\ 11,\ 7 $ となり、抽選の結果によっては条件を満たす。 - $ (4,\ 5,\ 2) $ のケース；$ 2 $ 日目の点数が選手 $ 1 $ から順に $ 1,\ 3,\ 2,\ 4,\ 5 $ のとき、合計点は $ 7,\ 7,\ 3,\ 11,\ 7 $ となり、抽選の結果によっては条件を満たす。