Problem Statement

We have an integer sequence of length N: A=(A_1,A_2,\cdots,A_N). Below in this problem, let the score of A be the sum of the first K terms of A. Additionally, let s be the score of the sequence A given in input.

You can do the following operation any number of times.

• Choose two adjacent elements of A and swap them.

Your objective is to make the score at least s+1. Determine whether the objective is achievable. If it is, find the minimum number of operations needed to achieve it.

Constraints

• 2 \leq N \leq 4 \times 10^5
• 1 \leq K \leq N-1
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

4 2
2 1 1 2

Sample Output 1

2

We have s=2+1=3. The following sequence of operations makes the score at least 4.

• (2,1,1,2) \to (swap A_3 and A_4)\to (2,1,2,1) \to (swap A_2 and A_3)\to (2,2,1,1)

The objective is not achievable in one operation, so the minimum number of operations needed is 2.

Sample Input 2

3 1
3 2 1

Sample Output 2

-1

Sample Input 3

20 13
90699850 344821203 373822335 437633059 534203117 523743511 568996900 694866636 683864672 836230375 751240939 942020833 865334948 142779837 22252499 197049878 303376519 366683358 545670804 580980054

Sample Output 3

13

Problem Statement

Snuke is about to make an integer sequence of length N consisting of 0 and 1. He starts with an empty sequence x and does the following two kinds of operations N times in total, in any order he likes.

• Operation A: Flip every element of x, that is, convert each 0 to 1 and vice versa. Then, add 0 to the beginning of x.
• Operation B: Add 0 to the end of x.

You are given an integer sequence of length N consisting of 0 and 1: A=(A_1,A_2,\cdots,A_N). Determine whether it is possible to make x equal to A.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 1
• All values in input are integers.

Sample Input 1

4
0 1 1 0

Sample Output 1

Yes

Snuke can do the following.

• Start with x=()
• Do operation A, making x=(0).
• Do operation B, making x=(0,0).
• Do operation A, making x=(0,1,1).
• Do operation B, making x=(0,1,1,0).

Sample Input 2

4
1 0 0 0

Sample Output 2

No

Sample Input 3

4
0 0 0 1

Sample Output 3

No

Problem Statement

There are N cards, indexed 1 to N. Card i has an integer A_i written on it. Here, N is even.

Snuke and Mr. Min will play a game. The game consists of N turns, alternately taken by the two players, with Snuke going first. In each turn, the player does the following operation.

• In Snuke's turn: He takes any card of his choice that is not taken by anyone yet.
• In Mr. Min's turn: He takes the card with the minimum index that is not taken by anyone yet.

Snuke's score will be the sum of the integers written on the cards taken by Snuke. Snuke plays optimally to maximize the score.

Incidentally, being a big fan of Snuke, you are planning to do something nasty to maximize the score. Specifically, before the start of the game, you will do the following action once.

• Choose an integer k (0 \leq k \leq N-1) and cyclically shift the integers written on the cards by k to the left: the cards 1,2,\cdots,N will have A_{k+1},A_{k+2},\cdots,A_N,A_1,\cdots,A_k written on them.

Find the value k that you should choose to maximize the score, and the resulting score when choosing that k.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N is even.
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

4
3 4 1 2

Sample Output 1

1 7

If you choose k=1, the cards 1,2,3,4 will have 4,1,2,3 written on them. Then, the game will go as follows.

• Snuke takes Card 1.
• Mr. Min takes Card 2.
• Snuke takes Card 4.
• Mr. Min takes Card 3.

In this case, Snuke's score is 7.

In this input, k=2,3 will also be accepted.

Sample Input 2

2
1 1

Sample Output 2

0 1

Sample Input 3

10
716893678 779607519 555600775 393111963 950925400 636571379 912411962 44228139 15366410 2063694

Sample Output 3

7 3996409938

Problem Statement

You are given integers N and K. Determine whether there exists a permutation P=(P_0,P_1,\cdots,P_{2^N-1}) of (0,1,\cdots,2^N-1) satisfying the condition below, and construct one such sequence if it exists. Note that P is 0-indexed.

• For every i (0 \leq i \leq 2^N-1), P_i and P_{i+1 \mod 2^N} differ by exactly K bits in binary representation. The comparison is made after zero-padding both integers to N bits.

Constraints

• 1 \leq K \leq N \leq 18
• All values in input are integers.

Sample Input 1

3 1

Sample Output 1

Yes
0 1 3 2 6 7 5 4

Here, we have P=(000,001,011,010,110,111,101,100) in binary representation.

We can see that P_1=001 and P_2=011, for example, differ by exactly 1 bit, satisfying the condition for i=1. The same goes for every i.

Sample Input 2

2 2

Sample Output 2

No

Problem Statement

You are given integers N and K. Let us call an integer sequence A=(A_1,A_2,\cdots,A_N) good when it satisfies all of the conditions below.

• 0 \leq A_i \leq i (1 \leq i \leq N)
• For every integer v=1,2,\cdots,N, there is at most one index i such that A_i=v.

Find the sum, modulo (10^9+7), of the answers to the following problem for all good sequences A.

• Find the number of length-K (not necessarily contiguous) subsequences of A consisting of positive integers that are decreasing. In other words, find the number of sequences of indices 1 \leq i_1 < i_2 < \cdots < i_K \leq N such that A_{i_1}>A_{i_2}>\cdots>A_{i_K} \geq 1.

Constraints

• 3 \leq N \leq 5000
• 2 \leq K
• 2K-1 \leq N
• All values in input are integers.

Sample Input 1

3 2

Sample Output 1

1

For example, A=(0,2,1) is a good sequence, with one subsequence satisfying the condition. There are other good sequences such as A=(0,1,0),(1,2,3),(0,0,0), but none of them has subsequences satisfying the condition. In the end, no good sequence other than A=(0,2,1) has subsequences satisfying the condition, so the answer is 1.

Sample Input 2

6 2

Sample Output 2

660

Sample Input 3

10 3

Sample Output 3

242595

Sample Input 4

100 10

Sample Output 4

495811864

Problem Statement

There are N points in a plane, the i-th (1 \leq i \leq N) of which is (i,P_i). Here, (P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).

You can arrange a non-empty set s of points, which is a recursive operation defined as follows.

• If s contains exactly one point, arranging it creates a sequence composed of just that point.
• If s contains two or more points, arranging it creates a sequence composed of those points by doing one of the following two operations.
  • Choose any integer x and divide s into two: the set a of points whose X-coordinates are less than x and the set b of the other points. Here, neither a nor b should be empty. Create a sequence by concatenating the sequence obtained by arranging a and the sequence obtained by arranging b in this order.
  • Choose any integer y and divide s into two: the set a of points whose Y-coordinates are less than y and the set b of the other points. Here, neither a nor b should be empty. Create a sequence by concatenating the sequence obtained by arranging a and the sequence obtained by arranging b in this order.

Find the number, modulo (10^9+7), of sequences that can be obtained by arranging the set of points \{(1,P_1),(2,P_2),\cdots,(N,P_N)\}.

Constraints

• 1 \leq N \leq 30
• (P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
• All values in input are integers.

Sample Input 1

3
3 1 2

Sample Output 1

3

The following three sequences can be obtained.

• ((1,3),(2,1),(3,2))
• ((2,1),(3,2),(1,3))
• ((2,1),(1,3),(3,2))

For example, the sequence ((2,1),(1,3),(3,2)) can be obtained as follows.

• Arrange the set \{(1,3),(2,1),(3,2)\} by dividing it to the set of points whose Y-coordinates are less than 2 (=\{(2,1)\}) and the set of the other points (=\{(1,3),(3,2)\}).
  • Arrange the set \{(2,1)\} to obtain the sequence ((2,1)).
  • Arrange the set \{(1,3),(3,2)\} by dividing it to the set of points whose X-coordinates are less than 3 and the set of the other points.
    • Arrange the set \{(1,3)\} to obtain the sequence ((1,3)).
    • Arrange the set \{(3,2)\} to obtain the sequence ((3,2)).
    • Concatenate the resulting two sequences to obtain the sequence ((1,3),(3,2)).
  • Concatenate the resulting two sequences to obtain the sequence ((2,1),(1,3),(3,2)).

Sample Input 2

5
1 2 3 4 5

Sample Output 2

1

Sample Input 3

10
3 6 4 8 7 2 10 5 9 1

Sample Output 3

1332

Sample Input 4

30
7 11 8 26 4 13 28 5 14 1 16 27 10 2 23 25 17 6 3 18 24 15 9 22 21 29 12 20 19 30

Sample Output 4

641915679