Dropbox stores a user's images in a collection of databases within our datacenter. The databases are physically constructed as a row of racks - e.g. a sample collection consisting of 4 racks would look like the following:

A-B-C-D

Whenever a user uploads an image, we save the image across multiple adjacent databases. When we do this, we must replicate the image across the databases adjacent to each other. For example, if we decide to replicate the image across 2 databases, we can select from the following database sets: [AB] [B,C] [C,D). (A-C or B-D is not allowed because they are not adjacent). 

Each database has its own remaining space available. E.g:

A (1MB) -B (5MB) - C (3MB) - D (2MB). 

Because each set of databases have a differing remaining space available, and we are replicating the image, the size of the image that can be saved will be limited by the minimum space remaining across the selected database sets. For example, if we are looking at the [A B] database set, the largest image that can be saved is 1MB.

Given: 

int n: number of databases 

array db: remaining space for each database 

int x: number of replications 

Find the largest image that can be stored. Here is an example following the A-B-C-D set above: 

Example 

n = 4, the number of databases 

db = (1,5,3,2] 

x = 2,the number of replications we want 

In this array of databases, the subarrays of size 2 are (1,5), (5,3), (3,2] Thus, the initial analysis returns 1,3,2 because those are the minima for the segments. Finally, the maximum of these values is 3. Therefore, the answer is 3. 

Function Description

Complete the function max_image_size in the editor below. 

segment has the following parameter(s): 

int xi the number of replications we want 

int n: the total number of databases 

int db[n]: list of remaining space for each database

Returns: 

int: the maximum of the minimum values of available space found while analyzing the In this array of databases, In segments of x. 

Tip: To get the maximum amount of points, you should find a solution with a better time complexity than O(n²) 

Constraints

• 1≤ n ≤ 10⁶

• 1 ≤ x ≤ n 

•1 ≤ db[i] ≤ 10⁹