25214번 - 크림 파스타

민겸이는 크림 파스타를 먹다가 다음과 같은 문제를 생각해냈다.

빈 배열 \(A\)가 있다. 민겸이는 \(A\)의 맨 뒤에 정수를 \(N\)번 추가하려고 한다. 수를 그냥 추가하기만 하면 재미없으니, 수를 추가할 때마다 1 ≤ \(i\) ≤ \(j\) ≤ \(|A|\) 를 만족하는 정수 \(i\), \(j\)에 대하여 \(A_j - A_i\)의 최댓값을 구하려고 한다. \(|A|\)는 배열 \(A\)의 현재 길이를 뜻하고, \(A_i\)는 민겸이가 \(i\)번째로 추가한 정수를 뜻한다.

민겸이가 식사를 마치기 전에 이 문제를 대신 풀어보자.

입력은 두 줄로 주어진다.

첫 번째 줄에는 민겸이가 배열에 추가하려는 정수의 개수 \(N\)이 주어진다.

두 번째 줄에는 \(A_1\)부터 \(A_N\)까지 \(N\)개의 정수가 공백으로 구분되어 주어진다.

각 \(A_i\)가 추가된 직후의 문제의 답 \(N\)개를 공백으로 구분하여 출력한다.

• 1 ≤ \(N\) ≤ 200,000
• 1 ≤ \(A_i\) ≤ 10⁹