Goblins Candies Game

In this problem, you are given ( N ) goblins, each holding a certain number of candies. The total number of candies is calculated as ( S = \sum_{i=1}^{N} candies_i ). Two players compete, and if both play optimally, the winner is determined solely by the parity of ( S ). If ( S ) is odd, the first player wins; if ( S ) is even, the second player wins.

The task is to compute the winner based on the input values.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer ( N ) (the number of goblins). The second line contains ( N ) space-separated integers representing the number of candies each goblin holds.

outputFormat

Output a single integer to standard output (stdout): output 1 if the first player wins (i.e., if the sum of candies is odd) or 2 if the second player wins (i.e., if the sum of candies is even).## sample

5
1 3 5 7 9

1