당신의 회사는 비디오 게임을 제작하는 회사로, 은하계를 누비는 퀘이사 사냥꾼들을 주제로 한 N개의 게임 시리즈로 엄청난 성공을 거두었습니다. 그 결과 명성과 부, 그리고 예상치 못한 골칫거리도 함께 얻게 되었습니다. 바로 어떤 유명한 SF 소설 작가가 당신의 게임을 원작으로 삼았던 계약에 대해, 너무 낮은 가격으로 저작권을 넘겼다고 주장하며 변호사를 동원해 계약 조항을 수정하려 한다는 것입니다.
계약서에 따르면, 작가가 게임 번호 i(즉, i = 1, 2, ..., N)에 대해 받는 보수는 정수 a_i입니다. 변호사들은 각 게임이 전작보다 더 성공했기 때문에 작가의 보수 또한 더 높아져야 한다고 주장합니다.
주주들의 불필요한 공포를 막기 위해, 그리고 논란을 최소화하기 위해, 당신은 다음과 같은 결정을 내렸습니다: 각 숫자 a₁, a₂, ..., aₙ의 뒤에 최소한의 숫자들을 덧붙여서 새로운 수열이 엄격하게 증가하는 수열(strictly increasing) 이 되도록 해야 합니다.
각 aᵢ에 덧붙일 숫자(와 그 개수)는 서로 다를 수 있으며, 어떤 수에는 아예 숫자를 덧붙이지 않아도 됩니다.
당신의 목표는 전체적으로 덧붙이는 숫자의 총 개수를 최소로 만드는 것입니다.
입력
첫 번째 줄에 하나의 정수 N이 주어집니다 (1 ≤ N ≤ 200,000).
그 다음 N줄에 걸쳐 정수 a₁, a₂, ..., aₙ이 주어집니다 (1 ≤ aᵢ ≤ 10⁹).
sk14cj 1년 전
당신의 회사는 비디오 게임을 제작하는 회사로, 은하계를 누비는 퀘이사 사냥꾼들을 주제로 한 N개의 게임 시리즈로 엄청난 성공을 거두었습니다. 그 결과 명성과 부, 그리고 예상치 못한 골칫거리도 함께 얻게 되었습니다. 바로 어떤 유명한 SF 소설 작가가 당신의 게임을 원작으로 삼았던 계약에 대해, 너무 낮은 가격으로 저작권을 넘겼다고 주장하며 변호사를 동원해 계약 조항을 수정하려 한다는 것입니다.
계약서에 따르면, 작가가 게임 번호 i(즉, i = 1, 2, ..., N)에 대해 받는 보수는 정수 a_i입니다. 변호사들은 각 게임이 전작보다 더 성공했기 때문에 작가의 보수 또한 더 높아져야 한다고 주장합니다.
주주들의 불필요한 공포를 막기 위해, 그리고 논란을 최소화하기 위해, 당신은 다음과 같은 결정을 내렸습니다: 각 숫자 a₁, a₂, ..., aₙ의 뒤에 최소한의 숫자들을 덧붙여서 새로운 수열이 엄격하게 증가하는 수열(strictly increasing) 이 되도록 해야 합니다.
각 aᵢ에 덧붙일 숫자(와 그 개수)는 서로 다를 수 있으며, 어떤 수에는 아예 숫자를 덧붙이지 않아도 됩니다.
당신의 목표는 전체적으로 덧붙이는 숫자의 총 개수를 최소로 만드는 것입니다.
입력
첫 번째 줄에 하나의 정수 N이 주어집니다 (1 ≤ N ≤ 200,000).
그 다음 N줄에 걸쳐 정수 a₁, a₂, ..., aₙ이 주어집니다 (1 ≤ aᵢ ≤ 10⁹).
출력
프로그램은 덧붙인 숫자의 총 개수의 최솟값을 하나의 정수로 출력해야 합니다.