Problem Statement  
Circle City consists of n buildings on a circle
You are given the int[] dist with n elements.
The elements of dist are the distances between adjacent buildings, in clockwise order around the circle.
Citizens can travel along the circle in both directions.
Their speed is one unit of distance per second.
You would now like to help them get around the city faster by building k teleporters.
Once you do so, it will be possible to travel between any two teleporters in zero time.
For the purpose of this problem, both buildings and teleporters are considered points.
Teleporters can be built anywhere on the circle, possibly at noninteger coordinates.
A teleporter may share its location with a building.
For any pair of buildings X and Y, let d(X,Y) be the shortest time a person will need to get from X to Y (or vice versa).
The diameter of Circle City is defined to be the maximum of all values d(X,Y).
Your task is to minimize the diameter of Circle City.
Find an optimal way to place the teleporters and compute and return the corresponding value of the diameter.
(It can be shown that the optimal diameter will always be an integer.)
  Definition   Class:  CircleCity  Method:  findMin  Parameters:  int[], int  Returns:  int  Method signature:  int findMin(int[] dist, int k)  (be sure your method is public) 
    Constraints    dist will contain between 2 and 2,000 elements, inclusive.    Each element of dist will be between 1 and 10^6, inclusive.    k will be between 2 and dist, inclusive.   Examples  0)     Returns: 3  Here is a picture of the above scenario:
The blue dots are the three buildings.
The two red circles show one optimal placement of the two teleporters.
One teleporter is exactly at the location of building C, the other is between A and B, and its distance from A is 0.6.
For this placement of teleporters we have d(A,B) = 3, d(A,C) = 0.6, and d(B,C) = 2.4.
Hence, the current diameter is 3.
It can be shown that this is optimal. 

 1)     Returns: 0  We can build the three teleporters right at the three buildings.


 2)    {1,2,3,4,5,6,5,4,3,2,1}  5 
 Returns: 5  
 3)    {1, 100, 1,1,1, 100, 1, 100, 1,1,1, 100, 1}  4 
 Returns: 3  
 4)    {3,1,4,1,5,9,2,6,5,3,5,8,9,7}  6 
 Returns: 8  
 5)    {
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000
}  7 
 Returns: 9000000  

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)2010, TopCoder, Inc. All rights reserved.
