## DMOPC '21 Contest 10 P6 - Median Replace

View as PDF

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem types

You are given an array of positive integers , initially all distinct. You can repeatedly perform the following operation:

• Choose a subarray with where the size is odd and are all distinct. Replace all of with their median.

Determine

1. The minimum number of distinct numbers in after performing a finite number of operations.
2. The maximum number of operations performed among all sequences of operations that achieve the minimum in (1). It can be proven that this answer is finite.
3. The number of sequences of operations that achieve both the minimum in (1) and the maximum in (2), modulo .

#### Constraints

All are pairwise distinct.

#### Input Specification

The first line contains the integer .

The second line contains space-separated integers .

#### Output Specification

Output space-separated integers, the answers to (1), (2), and (3) in order.

#### Sample Input

6
3 1 4 2 5 6

#### Sample Output

2 2 3

#### Explanation

The sequences of operations are:

• : The array becomes .
• : The array becomes .
• : The array becomes .