캐나다에 사는 타블로의 집처마밑에 거대한 고드름이 생겼다. 드문 기회이기 때문에, 타블로는 고드름을 조사해 보기로 했다. 타블로의 집처마 밑에는 N개 (2≤N≤100,000)의 고드름이 생겼다. 이 고드름들은 일직선위에 늘어서 있고 처마밑의 왼쪽부터 i cm (1≤i≤N)의 위치에 i개의 고드름이 있다. i개의 고드름의 길이는 처음에 a_i cm (a_i는 1이상의 정수)이다. 이 고드름들은 다음 규칙들에 따라 자라난다.

* i개의 고드름은 i-1개째의 고드름과 i+1개의 고드름 양쪽보다 긴 경우에만 1시간에 1cm씩 늘어난다. (단, 양쪽끝의 고드름의 경우에는 한쪽옆의 고드름만을 생각한다. 즉, 1번째 고드름은 2번째 고드름보다 길면 늘어나고, N번째 고드름은 N-1번째 고드름보다 길이가 길 경우에 늘어난다.)

* 어떤 고드름도 L cm (2≤L≤50,000)에 도달한 순간 뿌리쪽에서 부러진다. (부러진 고드름은 이후 길이 0cm의 고드름이 된다.)

처음 상태에선 이웃한 2개의 고드름의 길이는 모두 다르게 되어있다. 이 경우에 충분한 시간이 경과하면 N개의 고드름이 모두 부러져서 길이가 0cm가 된다. 타블로는 고드름이 이와 같은 상태가 될때까지의 시간을 알고싶다.

N개의 고드름이 최초의 길이와 고드름의 한계길이가 주어졌을때 모든 고드름이 부러질때까지 걸린 시간을 구하는 프로그램을 작성하여라.

#2338 upload 14 done 4 how_to_reg 4

고드름 timer 1s memory - MB

#2338

고드름 1s - MB