409705: GYM103688 G Chevonne's Necklace

For her excellent performance, pianist Chevonne was awarded a pearl necklace. The necklace consisted of $$$n$$$ pearls which form a circle and are numbered $$$1, 2, \cdots, n$$$ clockwise.

To prevent the pearls from being covered with dust, she wants to move pearls from the necklace and wipe them. However, the way to remove the pearls is complex because of their uniqueness of them.

Specifically, every pearl on the necklace has a continuity value $$$c_i ~ (c_i \geq 0)$$$. Each turn, Chevonne can choose a pearl $$$i$$$ with $$$c_i \geq 1$$$ and move the pearl $$$i$$$ and $$$c_i - 1$$$ clockwise consecutive pearls ($$$c_i$$$ pearls in all). Be careful! If the number of remaining pearls is less than $$$c_i$$$, she will be unable to choose pearl $$$i$$$. After that, the remaining pearls will form a new circle.

Chevonne will repeat the process till she can't remove any pearls or all the pearls have been removed. She is curious about the maximum number of pearls she could remove and the number of such solutions.

Here, we use a set to describe a solution. The set contains the number $$$i$$$ if Chevonne chose pearl $$$i$$$ in some step. Two solutions are different if and only if the sets are different.

The first line of input contains one positive integer $$$n~(1 \leq n \leq 2000)$$$.

The following one line contains $$$n$$$ non-negative integers separated by spaces. The $$$i$$$-th number represents $$$c_i~(0 \leq c_i \leq 2000)$$$. Pearls are numbered clockwise from $$$1$$$ to $$$n$$$.

Please output two integers separated by one space.

The first one is the maximum number of pearls Chevonne could remove and the second one is the number of such solutions. Since the number of solutions may be very large, please output it modular $$$998244353$$$.

6
0 1 1 3 3 1

6 3

In the example, all the pearls could be removed by Chevonne, the $$$3$$$ possible solutions are shown as follows:

1. remove the $$$2, 3, 6, 4$$$-th pearl in order.
2. remove the $$$2, 3, 6, 5$$$-th pearl in order.
3. remove the $$$5, 4$$$-th pearl in order.