Colored Pencils - Repovive Starter Round 9 | Repovive

25E. Colored Pencils

2500 pts2s256 MB

There are $n$ children and $m$ colored pencils. The colors are numbered from $1$ to $m$ , and there is exactly one pencil of each color.

Each child wants to draw one line with each color. Child $i$ must use the colors in the order $a_i, a_i+1, \ldots, m, 1, \ldots, a_i-1$ .

Drawing one line takes exactly one minute. During each minute, each child can use at most one pencil, and each pencil can be used by at most one child. Children may wait before drawing their first line or between drawing two lines.

Find the minimum number of minutes needed for all children to finish drawing.

Constraints

$1 \le t \le 10^4$
$1 \le n,m \le 2 \times 10^5$
$1 \le a_i \le m$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
The sum of $m$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \quad m \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

3 4
1 1 1

Case 2

4 4
1 2 3 4

Explanation

Case 1

The children can start in minutes $1$ , $2$ , and $3$ , then each draws for four consecutive minutes. They finish in minutes $4$ , $5$ , and $6$ . The last child to use pencil $1$ cannot do so before minute $3$ and needs three more minutes, so fewer than $6$ minutes is impossible.

Case 2

All four children can draw without waiting. In each minute, they use four different pencils, so everyone finishes after $4$ minutes. Each child needs four lines, so this is optimal.

Output

Case 1

Case 2

Input

Case 1

6 4
1 1 1 3 3 3

Case 2

1 5
4

Case 3

5 1
1 1 1 1 1

Explanation

Case 1

One schedule is shown below. A dash means that the child does not draw during that minute.

Child	Minute 1	Minute 2	Minute 3	Minute 4	Minute 5	Minute 6	Minute 7
1	1	2	-	3	4	-	-
2	-	1	2	-	3	4	-
3	-	-	1	2	-	3	4
4	3	4	-	1	2	-	-
5	-	3	4	-	1	2	-
6	-	-	3	4	-	1	2

Every child still needs at least one line after using pencil $3$ . That pencil must be used six times, so the last of these uses cannot finish before minute $6$ . At least $7$ minutes are necessary.

Case 2

The only child uses colors $4,5,1,2,3$ in five consecutive minutes. Five lines require at least $5$ minutes.

Case 3

The children take turns using the only pencil. Exactly $5$ minutes are needed.

Output

Case 1

Case 2

Case 3

There are $n$ children and $m$ colored pencils. The colors are numbered from $1$ to $m$ , and there is exactly one pencil of each color.

Each child wants to draw one line with each color. Child $i$ must use the colors in the order $a_i, a_i+1, \ldots, m, 1, \ldots, a_i-1$ .

Find the minimum number of minutes needed for all children to finish drawing.

$1 \le t \le 10^4$
$1 \le n,m \le 2 \times 10^5$
$1 \le a_i \le m$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
The sum of $m$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \quad m \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

All four children can draw without waiting. In each minute, they use four different pencils, so everyone finishes after $4$ minutes. Each child needs four lines, so this is optimal.

One schedule is shown below. A dash means that the child does not draw during that minute.

Child	Minute 1	Minute 2	Minute 3	Minute 4	Minute 5	Minute 6	Minute 7
1	1	2	-	3	4	-	-
2	-	1	2	-	3	4	-
3	-	-	1	2	-	3	4
4	3	4	-	1	2	-	-
5	-	3	4	-	1	2	-
6	-	-	3	4	-	1	2

Every child still needs at least one line after using pencil $3$ . That pencil must be used six times, so the last of these uses cannot finish before minute $6$ . At least $7$ minutes are necessary.

The only child uses colors $4,5,1,2,3$ in five consecutive minutes. Five lines require at least $5$ minutes.

The children take turns using the only pencil. Exactly $5$ minutes are needed.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

25E. Colored Pencils

Constraints

Input

Output

Samples

25E. Colored Pencils

Constraints

Input

Output

Samples