Woburn Challenge 2018-19 Round 2 - Senior Division

Ethan Hunt has traced a string of illegal plutonium trafficking down to a remote warehouse situated on a frigid island in Nunavut!

The warehouse has been operating for a period of ~N~ (~1 \le N \le 200\,000~) days, and it had ~P_i~ (~1 \le P_i \le 10^6~) boxes of plutonium in stock at the end of the ~i~-th day.

At the end of the first day, there was a single box (~P_1 = 1~). On each subsequent day ~i~ (~2 \le i \le N~), it's possible that a buyer came to withdraw all of the plutonium in the warehouse in the morning. Whether or not that occurred, one new box of plutonium then arrived at the warehouse in the afternoon. In other words, if a withdrawal occurred on day ~i~, then ~P_i = 1~, and otherwise, ~P_i = P_{i-1} + 1~.

Ethan has entrusted the task of monitoring the warehouse to his friend and fellow IMF member Luther Stickell. Accurately monitoring the warehouse proved problematic, but Luther did his best to come up with a list of observations ~O_{1 \dots N}~ ~(0 \le O_i \le 10^6)~. If ~O_i = 0~, then Luther has no idea how much plutonium the warehouse had in stock at the end of the ~i~-th day. Otherwise, if ~O_i > 0~, then Luther believes that the warehouse had exactly ~O_i~ boxes of plutonium in stock at the end of the ~i~-th day (in other words, that ~P_i = O_i~).

Ethan would now like to use Luther's observations to determine how many sellers withdrew plutonium from the warehouse. Due to gaps in Luther's observations, there may be multiple sequences of events which are consistent with them, so Ethan is interested in both the minimum and maximum possible number of withdrawals which could have taken place over the course of days ~2 \dots N~. It's also possible that Luther's observations are inconsistent with any possible sequence of events.

Subtasks

In test cases worth ~6/20~ of the points, ~N \le 20~.
In test cases worth another ~8/20~ of the points, ~N \le 2\,000~.

Input Specification

The first line of input consists of a single integer, ~N~.
The next line consists of ~N~ integers, ~O_{1 \dots N}~.

Output Specification

Output either two integers, the minimum and maximum possible number of withdrawals, or the single integer -1 if it's impossible for Luther's observations to be accurate.

Sample Input 1

6
1 0 0 0 3 0

Sample Output 1

1 3

Sample Input 2

3
1 0 4

Sample Output 2

-1

Sample Explanation

In the first case, it's possible that plutonium was only withdrawn a single time, on the morning of the ~3~rd day. It's also possible for as many as ~3~ withdrawals to have taken place, on the mornings of the ~2~nd, ~3~rd, and ~6~th days.

In the second case, the warehouse could contain at most ~3~ boxes of plutonium at the end of the ~3~rd day (if no withdrawals had taken place), which is inconsistent with Luther's observed count of ~4~.