Practice Loops and Cycle detection with the exercise "Bulgarian solitaire"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

Goal

In Bulgarian solitaire you are given piles of cards. In each turn you do 2 steps:
Step 1: Take a card from each pile. Piles with no cards are ignored.
Step 2: Make a new pile with the cards taken in Step 1.

You repeat the steps until you find a loop, meaning a configuration which has appeared previously. Again, piles with no cards are ignored. Also, ordering is not important, e.g. 1 card in the first pile and 2 cards in the second pile is considered the same as 2 cards in the first and 1 card in the second.

Card values are irrelevant.

The goal of this puzzle is to find the length of the loop (there is always a loop).

In the examples below, Turn 0 refers to the starting number of cards in each pile, and the other Turns refer to the number of cards in each pile (including a newly created pile) after each turn.

Example 1:

Turn 0 | 3
Turn 1 | 2 1
Turn 2 | 1 0 2

Ignoring ordering and piles with no cards, Turn 1 and Turn 2 show the same configuration of 1 2. The length of the loop is 1.

Example 2:

Turn 0 | 1 3 3 4
Turn 1 | 0 2 2 3 4
Turn 2 | 0 1 1 2 3 4
Turn 3 | 0 0 0 1 2 3 5
Turn 4 | 0 0 0 0 1 2 4 4
Turn 5 | 0 0 0 0 0 1 3 3 4

Ignoring ordering and piles with no cards, Turn 0 and Turn 5 show the same configuration of 1 3 3 4. The length of the loop is 5.

Example 3:

Turn 0 | 1 0 5 1
Turn 1 | 0 0 4 0 3
Turn 2 | 0 0 3 0 2 2
Turn 3 | 0 0 2 0 1 1 3
Turn 4 | 0 0 1 0 0 0 2 4
Turn 5 | 0 0 0 0 0 0 1 3 3
Turn 6 | 0 0 0 0 0 0 0 2 2 3

Ignoring ordering and piles with no cards, Turn 2 and Turn 6 show the same configuration of 2 2 3. The length of the loop is 4.

Reference: https://en.wikipedia.org/wiki/Bulgarian_solitaire

Input

Line 1: An integer N for the initial number of piles.
Line 2: N space-separated integers C representing the initial number of cards in each pile.

Output

Line 1: An integer representing the length of the loop.

Constraints

1 ≤ N ≤ 100

Example

Input

1
3

Output

Solve it

A higher resolution is required to access the IDE