D - Decrease 2 max elements Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の正整数列 A = (A_1, A_2, \dots ,A_N) が与えられます。高橋くんは、以下の操作を A に含まれる正の要素の個数が 1 つ以下になるまで繰り返します。

  • A を要素の降順に並び替える。それから、 A_1, A_2 を 1 減らす。

高橋くんが操作をする回数を求めてください。

制約

  • 2 \leq N \leq 100
  • 1 \leq A_i \leq 100
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ。

入力例 1

4
1 2 3 3

出力例 1

4

操作は以下のように進みます。

  • 1 回目の操作で A = (2, 2, 2, 1) となる。
  • 2 回目の操作で A = (1, 1, 2, 1) となる。
  • 3 回目の操作で A = (1, 0, 1, 1) となる。
  • 4 回目の操作で A = (0, 0, 1, 0) となる。A に含まれる正の要素の個数が 1 つ以下になったので、ここで操作を終了する。

入力例 2

3
1 1 100

出力例 2

2

Score : 200 points

Problem Statement

You are given a sequence of N positive integers A = (A_1, A_2, \dots ,A_N). Takahashi repeats the following operation until A contains one or fewer positive elements:

  • Sort A in descending order. Then, decrease both A_1 and A_2 by 1.

Find the number of times he performs this operation.

Constraints

  • 2 \leq N \leq 100
  • 1 \leq A_i \leq 100
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

4
1 2 3 3

Sample Output 1

4

The process goes as follows:

  • After the 1st operation, A is (2, 2, 2, 1).
  • After the 2nd operation, A is (1, 1, 2, 1).
  • After the 3rd operation, A is (1, 0, 1, 1).
  • After the 4th operation, A is (0, 0, 1, 0). A no longer contains more than one positive elements, so the process ends here.

Sample Input 2

3
1 1 100

Sample Output 2

2