The Ruthless Boss

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.

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.

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