DMOPC '21 Contest 10 P6 - Median Replace

View as PDF

Submit solution


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

Author:
Problem types

You are given an array of N positive integers a_1, a_2, \dots, a_N, initially all distinct. You can repeatedly perform the following operation:

  • Choose a subarray [l,r] with 1 \le l < r \le N where the size r-l+1 is odd and a_l, a_{l+1}, \dots, a_r are all distinct. Replace all of a_l, a_{l+1}, \dots, a_r with their median.

Determine

  1. The minimum number of distinct numbers in a_1, a_2, \dots, a_N 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 998\,244\,353.

Constraints

1 \le N \le 3 \times 10^6

1 \le a_i \le N

All a_i are pairwise distinct.

Subtask 1 [40%]

1 \le N \le 5 \times 10^3

Subtask 2 [30%]

1 \le N \le 2 \times 10^5

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line contains the integer N.

The second line contains N space-separated integers a_1, a_2, \dots, a_N.

Output Specification

Output 3 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 3 sequences of operations are:

  • [[1,3],[3,5]]: The array a becomes [3,1,4,2,5,6] \to [3,3,3,2,5,6] \to [3,3,3,3,3,6].
  • [[1,3],[4,6]]: The array a becomes [3,1,4,2,5,6] \to [3,3,3,2,5,6] \to [3,3,3,5,5,5].
  • [[4,6],[1,3]]: The array a becomes [3,1,4,2,5,6] \to [3,1,4,5,5,5] \to [3,3,3,5,5,5].

Comments

There are no comments at the moment.