Problem Description

It is the year 2212. The scale of competitive programming has expanded, and the International Olympiad in Informatics (IOI) has become famous worldwide!

This year's IOI has $ N $ participants. The competition lasts for 2 days.

• Day 1: A written test is conducted. Participant $ i $ scored $ A_i $ points. There were no ties in the written test.
• Day 2: A practical test is conducted. In the practical test, scores ranging from 1 to $ N $ are assigned to each participant based on their performance. The best performer gets $ N $ points, the second-best gets $ N - 1 $ points, and so on, with the worst performer getting 1 point.

You know the scores of the participants from Day 1. However, you do not know the scores of anyone from Day 2.
The rankings of the participants are determined as follows:

• Basically, participants with higher total scores rank higher. (However, the highest rank is 1 and the lowest rank is $ N $.)
• In case of ties, the ranking within the tied group is determined randomly.

The person who ranks 1st wins the gold medal, the person who ranks 2nd wins the silver medal, and the person who ranks 3rd wins the bronze medal.
You know one piece of information about the medalists, represented by $ P $ ($ P $ is either 1 or 2):

• If $ P = 1 $, when sorting the scores of the medalists from Day 1 in descending order, they are (gold, silver, bronze).
• If $ P = 2 $, when sorting the scores of the medalists from Day 1 in descending order, they are (gold, bronze, silver).

How many possible combinations of (gold medalist, silver medalist, bronze medalist) are there?

Input Format

The input is given from the standard input in the following format:

$ N $ $ P $ $ A_1 $ $ A_2 $ $ A_3 $ ... $ A_N $

Output Format

Output the number of possible combinations of (gold, silver, bronze) in one line.

Sample Input and Output

Sample Input #1

5 1
3 1 6 4 8

Sample Output #1

4

Sample Input #2

5 2
6 4 1 7 2

Sample Output #2

3

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

Notes/Hints

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 distinct.

Subtasks and Points

This problem has 2 subtasks:

1. (600 points): $ P = 1 $
2. (600 points): $ P = 2 $

Each subtask consists of 12 partial score datasets. Correct answers to all test cases satisfying the partial score conditions are considered as "correct for this partial score dataset".

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$

The score of the submitted source code is the sum of the points of the partial score datasets correctly solved for both subtasks.

Sample Explanation 1

There are 4 possible scenarios. Representing the gold medalist as participant $ i $, the silver medalist as participant $ j $, and the bronze medalist as participant $ k $ as $ (i, j, k) $:

• Case $ (5, 3, 1) $: If the scores on Day 2 are $ 3, 4, 2, 1, 5 $ from participant 1, the total scores are $ 6, 5, 8, 5, 13 $, satisfying the condition.
• Case $ (5, 3, 2) $: If the scores on Day 2 are $ 2, 4, 3, 1, 5 $ from participant 1, the total scores are $ 5, 5, 9, 5, 13 $, satisfying the condition depending on the lottery result.
• Case $ (5, 3, 4) $: If the scores on Day 2 are $ 1, 2, 3, 4, 5 $ from participant 1, the total scores are $ 4, 3, 9, 8, 13 $, satisfying the condition.
• Case $ (5, 4, 1) $: If the scores on Day 2 are $ 4, 2, 1, 3, 5 $ from participant 1, the total scores are $ 7, 3, 7, 7, 13 $, satisfying the condition depending on the lottery result.

Sample Explanation 2

There are 3 possible scenarios. Representing the gold medalist as participant $ i $, the silver medalist as participant $ j $, and the bronze medalist as participant $ k $ as $ (i, j, k) $:

• Case $ (4, 2, 1) $: If the scores on Day 2 are $ 1, 5, 3, 4, 2 $ from participant 1, the total scores are $ 7, 9, 4, 11, 4 $, satisfying the condition.
• Case $ (4, 5, 1) $: If the scores on Day 2 are $ 1, 2, 3, 4, 5 $ from participant 1, the total scores are $ 7, 6, 4, 11, 7 $, satisfying the condition depending on the lottery result.
• Case $ (4, 5, 2) $: If the scores on Day 2 are $ 1, 3, 2, 4, 5 $ from participant 1, the total scores are $ 7, 7, 3, 11, 7 $, satisfying the condition depending on the lottery result.

见题面 Input 部分

见题面 Output 部分