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]~.