길이 N인 양의 정수열 A_1,\dots,A_N이 주어진다. 이 수열을 오름차순으로 만들려 한다.

수열 A_1,\dots,A_N이 오름차순이라는 것은, 각 i (1\le i \le N-1)에 대해 A_i \le A_{i+1}이라는 것이다.

수열 A를 오름차순으로 만들기 위해, 수열 A에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.

연산을 최소 횟수로 적용해서 A를 오름차순으로 만들고 싶다. 이때, 최소 횟수를 구하라.

[제약 조건]

주어지는 모든 수는 정수이다.

1 \le N \le 250,000

1 \le A_i \le 1,000,000 (1\le i \le N)

두 배 timer 2s memory 1024MB

두 배 2s 1024MB