The Ruthless Boss

Interview

Time limit2sMemory limit512 MB

Summary

Given n distinct deadlines, find the largest integer k so that scheduling all jobs, each taking exactly k hours back to back, meets every deadline.

Level: Medium5 of 10
Topics: Greedy, Sorting, Binary search, Math
Solved: No attempts yet

Problem

zych runs Namgyu Company and is known for working the staff to the bone. Today zych is again planning how to squeeze more hours out of them.

The company has $n$ jobs, and every job has its own deadline. Missing a deadline costs a contract penalty, so all $n$ jobs have to be finished. Spending too little time on a job lowers the quality of the result, so zych wants the staff to spend as much time as possible on each one. Different durations confuse the staff, so every job takes exactly $k$ hours.

Work starts at time $0$ and the jobs run one at a time, back to back with no idle gap. A job with deadline $A_i$ must finish at a time no later than $A_i$ . You choose the order of the jobs.

Given the $n$ deadlines, print the largest integer $k$ for which every job finishes by its deadline.

Input

The first line contains the number of jobs $n$ . ( $1 \le n \le 50000$ )

The second line contains the deadlines $A_1, A_2, \dots, A_n$ , separated by spaces. ( $1 \le A_i \le 1000000000$ ) No two jobs share a deadline.

Output

Print the largest integer $k$ for which every job finishes by its deadline.

Examples4

Example 1
Input
```
5
1 2 3 4 5
```
Expected output
```
1
```
Example 2
Input
```
1
1
```
Expected output
```
1
```
Example 3
Input
```
2
3 2
```
Expected output
```
1
```
Example 4
Input
```
3
10 20 30
```
Expected output
```
10
```