Stone Transfer Game

Charlie and Dan are playing a game on N piles of stones, numbered from 1 to N from left to right. Each pile has a positive number of stones. The players take turns, with Charlie moving first.

In each turn, the current player must remove a positive number of stones from the leftmost non‐empty pile among piles 1 to N−1, and transfer the removed stones to the adjacent right pile. However, if at the beginning of a player’s turn the only non‐empty pile is the Nth pile, then that player loses the game.

Under optimal play for both players, determine who will win the game.

Game Details:

• Piles are numbered 1 through N and each contains a positive integer number of stones.
• On a turn, the player identifies the leftmost pile (among piles 1 to N−1) that is non‐empty. From that pile, they remove any positive number of stones (at most the current number of stones in that pile) and add them to pile i+1.
• If at the start of a turn the only non‐empty pile is the Nth pile, the current player loses.

Hint: It turns out that only the counts in the first N−1 piles matter. Let c be the number of consecutive piles (from pile 1 onward) that have exactly 1 stone. If all the first N−1 piles have 1 stone then the winner is decided by whether N−1 is odd (in which case Charlie wins) or even (in which case Dan wins). Otherwise, if c is the count of initial ones before the first pile with more than one stone appears, then if c is even, Charlie can force a win; if c is odd, Dan will win.

Input-Output Note: In every game, output Charlie if the first player (Charlie) wins under optimal play, otherwise output Dan.

inputFormat

The first line contains a single integer N (2 ≤ N ≤ 10⁵), the number of piles.

The second line contains N space‐separated positive integers: a₁, a₂, …, a_N, where a_i denotes the number of stones in the i-th pile.

outputFormat

Output a single line containing either Charlie if the first player wins under optimal play, or Dan otherwise.

sample

2
1 5

Charlie