Training Site

# Tournament

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 6.0 seconds

Toddy is a competitive Rock Paper Scissors player, and he's entering a local tournament next week! The tournament uses a single-elimination format. This means the winners of each match will play another in the next round, while the losers are immediately eliminated.

There are $N$ players and $K$ rounds ($N = 2^K$). The bracket structure works as follows:

• In the first round, there are half as many matches as players – match 1 between players 1 and 2, match 2 between players 3 and 4, etc.
• In the second round, there are a quarter as many matches as players – match 1 between the winners of matches 1 and 2 from the first round, match 2 between the winners of matches 3 and 4 from the first round, etc.

More formally, in the first round, match $m$ is played between players $2m-1$ and $2m$. Then, match $m$ of round $r$ is fought between the winners of matches $2m-1$ and $2m$ from round $r-1$ ($1 \leq m \leq 2^{K-r}$, $2 \leq r \leq K$).

As everyone knows, Rock Paper Scissors is a game of pure skill, so in any match between two players, the player with the higher skill level will always win. While Toddy might not be the best player, he does happen to know the skill level of every player in the tournament.

Toddy is good friends with the tournament director, who has agreed to let Toddy secretly change the tournament bracket before it is finalised. To minimise suspicion, he will only be allowed to make a single swap of the positions of any two players (including himself, who is always the first player in the bracket). Toddy would like to maximise the number of matches he can win, but if any single swap cannot help him win more matches than he already could, he will leave the bracket as it is.

Help Toddy determine the maximum number of matches he can win, and if swapping helps, the number of different ways he can swap players in order to achieve his goal. Note that swaps of players $(x,y)$ and $(y,x)$ are counted as the same swap.

## Input

The first line contains two space-separated integers: $N$, the number of players, and $K$, the number of rounds in the tournament ($2 \leq N \leq 65536$, $N = 2^K$)

The next line contains $N$ space-separated integers $x_i$, the $i$-th of which represents the skill level of the $i$-th player in the tournament bracket ($0 \leq x_i \leq 10^9$). It is guaranteed that each player's skill level is distinct. Toddy is always the first player in the bracket.

## Output

The first line should contain a single integer – the maximum number of matches Toddy can win by swapping any two players in the tournament bracket.

The second line should contain a single integer – the number of different ways Toddy can swap players in order to win the maximum number of matches possible. If swapping players does not help Toddy win any more matches than he already could, you should output $-1$ instead.

• Subtask 1 (35%): $2 \leq N \leq 64$
• Subtask 2 (35%): $2 \leq N \leq 2048$
• Subtask 3 (30%): $2 \leq N \leq 65536$

## Sample Explanation

In the first sample case, Toddy can win at most 1 match, by making any of the following 4 swaps: $(1,3), (1,4), (2,3), (2,4)$. For example, swapping Toddy (player 1) with player 3 allows him to win against player 4, but in the second round he would lose to player 2.

In the second sample case, Toddy is the strongest player, so swapping is not necessary – he will always win 2 matches.

In the third sample case, Toddy can win at most 2 matches, and the only way to achieve this is by swapping him with player 5. Then, he would win his first match against player 6, and his second match against player 7.

• ### Sample Input 1

4 2
54 86 23 49

1
4

• ### Sample Input 2

4 2
100 50 83 47

2
-1

• ### Sample Input 3

8 3
32 46 36 64 85 12 25 20

2
1