G - Medals Editorial /

Time Limit: 1 sec / Memory Limit: 976 MB

配点：1200 点

問題文

時は 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 は 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 つの小課題の「正解した部分点データセットの点数の合計」を足し算した値です。

入力

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

N P
A_1 A_2 A_3 ... A_N

出力

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

入力例 1

5 1
3 1 6 4 8

出力例 1

4

次の 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 となり、抽選の結果によっては条件を満たす。

入力例 2

5 2
6 4 1 7 2

出力例 2

3

次の 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 となり、抽選の結果によっては条件を満たす。

入力例 3

10 1
6 4 11 14 3 17 13 18 8 10

出力例 3

26

入力例 4

10 2
18 14 19 4 12 1 7 15 9 5

出力例 4

14

Max Score：1200 points

Problem Statement

In 2212, competitive programming is much more famous than now, and International Olympiad of Informatics (IOI) is one of the most famous contest in the world.

This year, N contestants, whose ID is numbered from 1 to N, participated in IOI.

The competition is held on 2 days as follows:

  • Day 1: There is a paper test. Contestant i got A_i points. It is guaranteed that A_i \neq A_j (1 \leq i < j \leq N).
  • Day 2: There is a practical test. In this test, score between 1 and N will be granted for each contestant. The contestant who performed the best will get N points, the contestant who performed the second best will get N - 1 points, ..., and the contestant who performed the worst will get 1 points.

Currently, you knows Day-1 score of all participants. But you don't know any of Day-2 results.
In IOI-rule, the participants' final score is (the score of paper test) + (the score of practical test).

The rank of the contestant will be determined as follows:

  • Basically, the higher the final score is, the higher the rank is. (Note: The highest rank is 1, and the lowest rank is N.)
  • If there are tie score, the rank will be determined with random-lottery among the contestant who got the same score.

In addition, contestant who got rank 1 will get a gold medal, contestant who got rank 2 will get a silver medal, and contestant who got rank 3 will get a bronze medal.

He knows one more informations about the final standings in IOI 2212. The information is represented as one integer P (either 1 or 2).

  • Let X be the participant ID who got the gold medal.
  • Let Y be the participant ID who got the silver medal.
  • Let Z be the participant ID who got the bronze medal.
  • If P = 1, A_X > A_Y > A_Z is satisfied.
  • If P = 2, A_X > A_Z > A_Y is satisfied.

How many possible combinations of (X, Y, Z) are there?

Constraints

  • N is an integer between 5 and 1 \ 000 \ 000 (inclusive)
  • P is either 1 or 2
  • A_i is an integer between 1 and 1 \ 000 \ 000 \ 000 (inclusive)
  • All A_i are different.

Subtasks and scoring

In this problem, there are 2 subtasks as follows.

  1. (600 points)：P = 1
  2. (600 points)：P = 2

In each subtask, there are 12 datasets as follows.

  1. (50 points)：5 \leq N \leq 7
  2. (50 points)：5 \leq N \leq 15
  3. (50 points)：5 \leq N \leq 30
  4. (50 points)：5 \leq N \leq 70
  5. (50 points)：5 \leq N \leq 200
  6. (50 points)：5 \leq N \leq 600
  7. (50 points)：5 \leq N \leq 2 \ 000
  8. (50 points)：5 \leq N \leq 8 \ 000
  9. (50 points)：5 \leq N \leq 50 \ 000
  10. (50 points)：5 \leq N \leq 200 \ 000
  11. (50 points)：5 \leq N \leq 500 \ 000
  12. (50 points)：5 \leq N \leq 1 \ 000 \ 000

Note: In each datasets, there can be two or more testcases.

Input

Input is given from Standard Input in the following format: 

N P
A_1 A_2 A_3 ... A_N

Output

Print the number of possible combinations of (X, Y, Z).

Sample Input 1

5 1
3 1 6 4 8

Sample Output 1

4

Let B_i be the Day-2 score of contestant i.
There are 4 ways as follows. X is the ID of gold medalist, Y ID the id of silver medalist, and Z is the ID of bronze medalist.

  • (X, Y, Z) = (5, 3, 1). If B = (3, 4, 2, 1, 5), the final score will be 6, 5, 8, 5, 13. Therefore, it satisfies the condition.
  • (X, Y, Z) = (5, 3, 2). If B = (2, 4, 3, 1, 5), the final score will be 5, 5, 9, 5, 13. Therefore, depending on lottery, it is possible that satisfies the condition.
  • (X, Y, Z) = (5, 3, 4). If B = (1, 2, 3, 4, 5), the final score will be 4, 3, 9, 8, 13. Therefore, it satisfies the condition.
  • (X, Y, Z) = (5, 4, 1). If B = (4, 2, 1, 3, 5), the final score will be 7, 3, 7, 7, 13. Therefore, depending on lottery, it is possible that satisfies the condition.

Sample Input 2

5 2
6 4 1 7 2

Sample Output 2

3

There are 3 ways as follows.

  • (X, Y, Z) = (4, 2, 1). If B = (1, 5, 3, 4, 2), the final score will be 7, 9, 4, 11, 4. Therefore, it satisfies the condition.
  • (X, Y, Z) = (4, 5, 1). If B = (1, 2, 3, 4, 5), the final score will be 7, 6, 4, 11, 7. Therefore, depending on lottery, it is possible that satisfies the condition.
  • (X, Y, Z) = (4, 5, 2). If B = (1, 3, 2, 4, 5), the final score will be 7, 7, 3, 11, 7. Therefore, depending on lottery, it is possible that satisfies the condition.

Sample Input 3

10 1
6 4 11 14 3 17 13 18 8 10

Sample Output 3

26

Sample Input 4

10 2
18 14 19 4 12 1 7 15 9 5

Sample Output 4

14