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
- The minimum number of distinct numbers in after performing a finite number of operations.
- 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.
- The number of sequences of operations that achieve both the minimum in (1) and the maximum in (2), modulo .
Constraints
All are pairwise distinct.
Subtask 1 [40%]
Subtask 2 [30%]
Subtask 3 [30%]
No additional constraints.
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 .
Comments