Problem Statement

There are some animals standing in a line in the Zoo of Lviv. They are numbered from the left to the
right, starting from 0. Each of the animals has a label with some positive integer written on it.
For each valid i, animal number i has the integer label[i] written on its label.

The director of the zoo wants to choose some non-empty subset of the animals and send them as a gift
to another zoo. The following two requirements should be fulfilled: Each of the chosen animals must
have a label that is between lower and upper, inclusive.  For each integer x from lower to upper,
inclusive, there must be at least one animal in the set with label equal to x.

Suppose that we have already chosen the animals we want to send. If we look at the original line,
some of these animals might stand right next to each other. More precisely, there will be one or
more groups, where a group is a consecutive segment of animals we want to send away. If there are
multiple ways to choose the set of animals we'll send to the other zoo, the director prefers the one
with the smaller number of groups. (This is because when there are fewer groups, we can pack the
animals into transport cages faster.)

You are given the int[] label and the two ints lower and upper. If it is impossible to choose the
set in the way described above, return -1. Otherwise, return the minimum number of groups that the
set may contain.

Method signature: int getNumber(int[] label, int lower, int upper)
Time limit (s): 4.000
Memory limit (MB): 256
    
Constraints

- label will contain between 1 and 44 elements, inclusive.
- Each element of label will be between 1 and 47, inclusive.
- lower will be between 1 and 47, inclusive.
- upper will be between lower and 47, inclusive.

Examples

0)
    
{2, 1, 3}
1
3
Returns: 1
The only way to choose the subset is to choose all animals.


1)
    
{3, 4, 1, 3, 4, 2}
1
3
Returns: 2
In the optimal solution we send away animals #2, #3, and #5 (0-based indices). Animals #2 and #3 form one group, animal #5 forms the other.


2)
    
{3, 4, 3, 1, 6, 2, 5, 7, 5, 2}
2
6
Returns: 2


3)

{3, 1, 4}
2
4
Returns: -1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.