Problem Statement

You are given a permutation A=(A_1,\ldots,A_N) of (1,2,\ldots,N).
Transform A into (1,2,\ldots,N) by performing the following operation between 0 and N-1 times, inclusive:

• Operation: Choose any pair of integers (i,j) such that 1\leq i < j \leq N. Swap the elements at the i-th and j-th positions of A.

It can be proved that under the given constraints, it is always possible to transform A into (1,2,\ldots,N).

Constraints

• 2 \leq N \leq 2\times 10^5
• (A_1,\ldots,A_N) is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

5
3 4 1 2 5

Sample Output 1

2
1 3
2 4

The operations change the sequence as follows:

• Initially, A=(3,4,1,2,5).
• The first operation swaps the first and third elements, making A=(1,4,3,2,5).
• The second operation swaps the second and fourth elements, making A=(1,2,3,4,5).

Other outputs such as the following are also considered correct:

4
2 3
3 4
1 2
2 3

Sample Input 2

4
1 2 3 4

Sample Output 2

0

Sample Input 3

3
3 1 2

Sample Output 3

2
1 2
2 3

Problem Statement

In AtCoder Land, there are N popcorn stands numbered 1 to N. They have M different flavors of popcorn, labeled 1, 2, \dots, M, but not every stand sells all flavors of popcorn.

Takahashi has obtained information about which flavors of popcorn are sold at each stand. This information is represented by N strings S_1, S_2, \dots, S_N of length M. If the j-th character of S_i is o, it means that stand i sells flavor j of popcorn. If it is x, it means that stand i does not sell flavor j. Each stand sells at least one flavor of popcorn, and each flavor of popcorn is sold at least at one stand.

Takahashi wants to try all the flavors of popcorn but does not want to move around too much. Determine the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.

Constraints

• N and M are integers.
• 1 \leq N, M \leq 10
• Each S_i is a string of length M consisting of o and x.
• For every i (1 \leq i \leq N), there is at least one o in S_i.
• For every j (1 \leq j \leq M), there is at least one i such that the j-th character of S_i is o.

Sample Input 1

3 5
oooxx
xooox
xxooo

Sample Output 1

2

By visiting the 1st and 3rd stands, you can buy all the flavors of popcorn. It is impossible to buy all the flavors from a single stand, so the answer is 2.

Sample Input 2

3 2
oo
ox
xo

Sample Output 2

1

Sample Input 3

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

Sample Output 3

3

Problem Statement

You are given a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

Each cell is one of the following: a start cell, a goal cell, an empty cell, or an obstacle cell. This information is described by H strings S_1,S_2,\dots,S_H, each of length W. Specifically, the cell (i,j) is a start cell if the j-th character of S_i is S, a goal cell if it is G, an empty cell if it is ., and an obstacle cell if it is #. It is guaranteed that there is exactly one start cell and exactly one goal cell.

You are currently on the start cell. Your objective is to reach the goal cell by repeatedly moving to a cell adjacent by an edge to the one you are in. However, you cannot move onto an obstacle cell or move outside the grid, and you must alternate between moving vertically and moving horizontally each time. (The direction of the first move can be chosen arbitrarily.)

Determine if it is possible to reach the goal cell. If it is, find the minimum number of moves required.

More formally, check if there exists a sequence of cells (i_1,j_1),(i_2,j_2),\dots,(i_k,j_k) satisfying all of the following conditions. If such a sequence exists, find the minimum value of k-1.

• For every 1 \leq l \leq k, it holds that 1 \leq i_l \leq H and 1 \leq j_l \leq W, and (i_l,j_l) is not an obstacle cell.
• (i_1,j_1) is the start cell.
• (i_k,j_k) is the goal cell.
• For every 1 \leq l \leq k-1, |i_l - i_{l+1}| + |j_l - j_{l+1}| = 1.
• For every 1 \leq l \leq k-2, if i_l \neq i_{l+1}, then i_{l+1} = i_{l+2}.
• For every 1 \leq l \leq k-2, if j_l \neq j_{l+1}, then j_{l+1} = j_{l+2}.

Constraints

• 1 \leq H,W \leq 1000
• H and W are integers.
• Each S_i is a string of length W consisting of S, G, ., #.
• There is exactly one start cell and exactly one goal cell.

Sample Input 1

3 5
.S#.G
.....
.#...

Sample Output 1

7

As shown in the left figure, you can move as (1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(3,3)\rightarrow(3,4)\rightarrow(2,4)\rightarrow(2,5)\rightarrow(1,5), reaching the goal cell in 7 moves. It is impossible in 6 moves or fewer, so the answer is 7.

Note that you cannot take a path that moves horizontally (or vertically) consecutively without alternating as shown in the right figure.

Sample Input 2

3 5
..#.G
.....
S#...

Sample Output 2

-1

It is not possible to reach the goal cell.

Sample Input 3

8 63
...............................................................
..S...#............................#####..#####..#####..####G..
..#...#................................#..#...#......#..#......
..#####..####...####..####..#..#...#####..#...#..#####..#####..
..#...#..#..#...#..#..#..#..#..#...#......#...#..#..........#..
..#...#..#####..####..####..####...#####..#####..#####..#####..
................#.....#........#...............................
................#.....#........#...............................

Sample Output 3

148

Problem Statement

Takahashi has an integer x. Initially, x=0.

Takahashi may do the following operation any number of times.

• Choose an integer i\ (1\leq i \leq 9). Pay C_i yen (the currency in Japan) to replace x with 10x + i.

Takahashi has a budget of N yen. Find the maximum possible value of the final x resulting from operations without exceeding the budget.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq C_i \leq N
• All values in input are integers.

Sample Input 1

5
5 4 3 3 2 5 3 5 3

Sample Output 1

95

For example, the operations where i = 9 and i=5 in this order change x as:

0 \rightarrow 9 \rightarrow 95.

The amount of money required for these operations is C_9 + C_5 = 3 + 2 = 5 yen, which does not exceed the budget. Since we can prove that we cannot make an integer greater than or equal to 96 without exceeding the budget, the answer is 95.

Sample Input 2

20
1 1 1 1 1 1 1 1 1

Sample Output 2

99999999999999999999

Note that the answer may not fit into a 64-bit integer type.

Problem Statement

This problem is a harder version of Problem C. Here, the sequence is split into three subarrays.

You are given an integer sequence of length N: A = (A_1, A_2, \ldots, A_N).

When splitting A at two positions into three non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.

More formally, find the maximum sum of the following three values for a pair of integers (i,j) such that 1 \leq i < j \leq N-1: the count of distinct integers in (A_1, A_2, \ldots, A_i), the count of distinct integers in (A_{i+1},A_{i+2},\ldots,A_j), and the count of distinct integers in (A_{j+1},A_{j+2},\ldots,A_{N}).

Constraints

• 3 \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq N (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

5

If we let (i,j) = (2,4) to split the sequence into three subarrays (3,1), (4,1), (5), the counts of distinct integers in those subarrays are 2, 2, 1, respectively, for a total of 5. This sum cannot be greater than 5, so the answer is 5. Other partitions, such as (i,j) = (1,3), (2,3), (3,4), also achieve this sum.

Sample Input 2

10
2 5 6 4 4 1 1 3 1 4

Sample Output 2

9