Consider the following:

Given a set ** S_{1}** of positive integers, compute the

**minimum size**of a set

**(possibly equal to**

`S`_{2}**) so that**

`S`_{1}**.**

`F(S`_{1}) = F(S_{2})### Input

The first line of input contains the size of ** S_{1}**.

The second line of input contains the elements of

**, separated by spaces.**

`S`_{1}### Output

A single integer: the minimum size of ** S_{2}**.

### Constraints

- 1 ≤ the size of S
_{1}< 2^{19} - 1 ≤ every element of S
_{1}< 2^{19}

### Notes

- If you use C++ I/O streams, please add
`cin.sync_with_stdio(false);`

before reading the input, in order to improve I/O speed. - The elements of a set are distinct, by definition.

### Sample

Input | Output | Explanation |
---|---|---|

45 10 15 25 | 3 | S_{1} = {5, 10, 15, 25}F(S _{1}) = {5, 10, 15, 25, 27, 29, 31}S _{2} = {5, 10, 25}F(S _{2}) = {5, 10, 15, 25, 27, 29, 31} |

The first observation we can make is that ` 0 ≤ orSum(S') < 2^19` for any subset

`of`

**S'**`. Let's see if we can construct a set`

**S1**`, having`

**Q**`using the integer values from`

**0 ≤ orSum(Q) < 2^19**`. It is enough to consider for this all elements of`

**S1****which are**

`S1`**completely included**in

**. An element**

`Q`**is**

`x`**completely included**in a set

**if**

`S`**, i.e. there is no position**

`orSum(S) | x = orSum(S)``for which`

**0 ≤ i < 19****. If these are not enough to form**

`orSum(S) & 2^i == 0 and x & 2^i != 0`**, then we cannot obtain**

`Q`**at all.**

`Q` We now need to compute for each such ** Q** the orSum of all elements â€œcompletely includedâ€ in

**. We can compute**

`S1`**, where**

`dp[x] = orSum(dp[x - 2^i])`**and**

`0 ≤ i < 19`**. Remark: if**

`x & 2^i == 2^i`**belongs to**

`x`**, then**

`S1`**.**

`dp[x] = x` Now, ** S2** needs to contain all numbers

**having**

`x`**and**

`dp[x] = x`**This assures us that they cannot be generated by applying orSum on a subset of numbers from**

`orSum({dp[x - 2^i] where 0 ≤ i < 19 and x & 2^i == 2^i}) < x.`**, so they must be in**

`S1`**.**

`S2`