Optimizing Bessie's Sorting Time

Bessie is trying to sort an array of N integers a₁,a₂,…,aₙ (with \(1\le N\le 2\cdot10^5\) and \(1\le a_i\le10^{11}\)). Her method is rather unusual. In her own sorting process she repeatedly searches her pile for the minimum element. For a pile of p numbers, finding the minimum takes exactly \(p\) seconds. When she finds the minimum she removes it from her pile and appends it to the end of a new array.

To speed things up, Farmer John assigns some of the work to assistant cows. Bessie is allowed to partition the numbers arbitrarily into two disjoint groups:

• Bessie’s pile: She will process these numbers with her algorithm. If there are \(k\) numbers in her pile, her total time is \(T_B = \frac{k(k+1)}{2}\) seconds (since she spends \(k\) seconds on the first extraction, \(k-1\) on the next, and so on).
• Assistants’ pile: Each number \(a_i\) in this pile is immediately assigned to a distinct assistant cow. An assistant cow sleeps for \(a_i\) seconds and, upon waking, appends the number to the new array. All assistant cows work in parallel. If multiple assistants finish at the same time, they all add their numbers simultaneously.

However, if Bessie and an assistant cow finish adding at the same time, Bessie’s number is placed before the assistant’s number. In the end the new array will be formed by merging the two sequences (Bessie’s sequence and the assistants’ sequence) in the order in which the numbers are added.

Your task is to help Bessie partition the numbers between her and the assistants such that the final merged array is sorted in non‐decreasing order and the overall sorting time is minimized. The overall time is determined by the later of Bessie’s finishing time \(T_B\) and the maximum assistant sleep time.

Clarification: Suppose Bessie chooses to assign a contiguous prefix of the sorted input to the assistants and the remaining to herself. Let the sorted array be \(S[1\ldots N]\). If Bessie assigns the smallest \(r\) numbers (i.e. \(S[1], S[2],\ldots, S[r]\)) to the assistants and the remaining \(k=N-r\) numbers to herself, then the assistants complete at times exactly equal to their values, with the maximum being \(S[r]\) (if \(r>0\); if \(r=0\), no assistant is used). Bessie will finish her sequence in \(\frac{k(k+1)}{2}\) seconds. In order for the final merged array (where assistant numbers are added at time equal to their value and Bessie’s numbers are inserted in order with finishing times \(T₁, T₂,\ldots,T_k\) with \(T₁ = k, T₂ = 2k-1, \) etc.) to be sorted in non-decreasing order, it is necessary that all assistant-added numbers are inserted before Bessie’s numbers. (Note that if an assistant and Bessie complete simultaneously, Bessie’s number comes first, so if the last assistant number equals Bessie’s first number, then the order would be reversed unless the numbers are equal.)

Your goal is to choose a partition (which, as argued, can be assumed to be a contiguous prefix of the sorted order) so that the overall required time \[ T = \max\Bigl(\frac{(N-r)(N-r+1)}{2},\ S[r]\Bigr) \] (with the convention that \(S[0]=0\)) is minimized over all valid choices of \(r\) (where, for \(1\le r < N\), validity requires that either \(S[r] < N-r\) or if \(S[r] = N-r\) then the next number is equal to \(S[r]\), ensuring the final merged order remains sorted).

Find and output the minimized overall time.

inputFormat

The first line contains a single integer \(N\). The second line contains \(N\) space-separated integers \(a_1, a_2, \ldots, a_N\).

outputFormat

Output a single integer, the minimum number of seconds required to obtain a sorted array following the process described above.

sample

3
5 1 2

3