### Indian National Olympiad in Informatics

### Online Programming Contest, 2-3 April 2005

### Basic Division

Problem 2: Balance the Teams, *(K Narayan Kumar, CMI)*

Our friend the king has a fairly large army that is divided
into a number of battalions. Once a year, in order to ensure that
his army is fighting fit, he organises war exercises. Here the
army is divided into two teams and they fight each other in mock
battles.

Each team is a collection of battalions -- that is, each
battalion is to assigned to one team or the other and cannot be
broken up.

The sizes of these battalions are not all the same. Some of
them are huge while others are small. To ensure that the war
exercises are useful, the two teams should be of roughly the same
size. So he asks the minister to divide the battalions into two
teams in such a way that the difference in the total size of the
two teams is minimized.

For instance, suppose there are 6 battalions and their sizes are as
follows:

Battalion No Size
1 20
2 30
3 100
4 30
5 20
6 30

Then, by using Battalions 1 and 3 in one team and the other
four battalions in the other team, the minister would get one
team with size 120 and the other with size 110. Thus the
difference is sizes is 10. You can verify that this is the best
possible.

Your task is to help the minister to select the teams.

Input format

The first line of the input contains a single integer
*N* indicating the number of battalions. The following
*N* lines (lines 2,3,...,*N*+1) contain one
positive integer each. The integer on line *i*+1 indicates
the size of the *i*th battalion.

Output format

The first line of the output should be a single positive integer
indicating the minimum possible difference in the sizes of the two
teams. Following this there must be *N* lines (lines 2,
... *N*+1) of output, each containing a 0 or a 1. This is a
description of a grouping that yields this optimal difference. The
value on line *i*+1 describes whether battalion *i* goes
to team 0 or team 1. If there is more than one such optimal grouping
it suffices to describe any one.

Test data

You may assume that *N* ≤ 20.

Example

We now illustrate the input and output formats using the
above example:

Sample input:

6
20
30
100
30
20
30

Sample output:

10
0
1
0
1
1
1