울타리 칠하기

톰 소여는 폴리 이모 댁을 둘러싼 울타리를 칠하는 힘든 일을 돕도록 $n$명의 친구를 설득했다. 울타리는 1번부터 $k$번까지 번호가 붙은 $k$개의 연속한 널빤지로 이루어져 있고, $k$번 널빤지 다음에는 다시 1번 널빤지가 온다.

톰의 친구들은 매우 까다로워서, $i$번째 친구는 정확히 $a_i$개의 연속한 널빤지로 이루어진 구간을 칠할 수 있을 때에만 칠하기에 참여하겠다고 한다. 톰에게는 붓이 하나뿐이므로 친구들은 차례대로 칠하고, 맡은 구간 전체를 한 번에 칠한다. 톰이 할 일은 친구들을 부를 순서를 정하고, 각 친구가 칠할 연속한 널빤지의 개수를 정하는 것뿐이다.

톰의 친구들은 각자 아직 칠해지지 않은 널빤지든 앞선 친구가 이미 칠한 널빤지든 상관없이 칠할 준비가 되어 있다. 그래도 친구들은 아직 칠해지지 않은 널빤지를 칠할 때 더 즐거워한다. 톰은 수 $x$를 정하고 각 친구가 적어도 $x$개의 아직 칠해지지 않은 널빤지를 칠하도록 울타리 구간을 배분하려 한다. 톰은 친구들을 아끼기 때문에 모두가 칠하기에서 최대한 즐거움을 얻기를 바라므로, $x$를 최대화하려 한다.

톰이 친구들에게 얼마나 많은 즐거움을 줄 수 있는지 알아내도록 돕자.

입력 파일의 첫째 줄에는 두 정수 $n$ ($1 \le n \le 10^5$)과 $k$ ($1 \le k \le 10^9$)가 들어 있다. 다음 줄에는 $n$개의 정수, 즉 $a_i$ ($1 \le a_i \le k$)가 들어 있다.

최대로 가능한 $x$의 값을 한 개의 수로 출력한다.

첫 번째 예제에서 $x = 5$이다. 한 친구가 다섯 개보다 많은 널빤지를 칠하기를 원하지 않기 때문이다. 그가 먼저 와서 다섯 개를 칠하면, 아직 칠해지지 않은 널빤지 10개가 톰의 두 번째 친구에게 돌아간다. 남은 85개의 널빤지는 톰이 직접 칠해야 한다.

두 번째 예제에서 $x = 2$에 도달하는 방법의 예는 다음과 같다. 먼저 세 번째 친구가 4번부터 6번까지의 널빤지를 칠한다 (아직 칠해지지 않은 널빤지 3개). 그다음 네 번째 친구가 1번부터 5번까지의 널빤지를 칠한다 (아직 칠해지지 않은 널빤지 3개). 그다음 두 번째 친구가 1번부터 8번까지의 널빤지를 칠한다 (아직 칠해지지 않은 널빤지 2개). 마지막으로 첫 번째 친구가 6번부터 10번까지와 1번부터 2번까지의 널빤지를 칠한다 (아직 칠해지지 않은 널빤지 2개인데, 울타리가 원형으로 이어져 있어 이 널빤지들이 연속한 구간을 이룬다는 점에 주목하자).