2963 - All Odd, All Even

Created by Óscar Dávalos Orozco
Added by jicote (2014-06-16)
Limits
Total Time: 40000 MS | Test Time: 4000 MS |Memory: 62 MB | Output: 64 MB | Size: 14 KB
Enabled languages
Available in

Description

All odd, all even is a game that consists in convert all the integers x1, x2, x3,…, xN to odd numbers or to even numbers. To do this, the only operation you are allowed to do is to choose an integer xK and add 1 to xK and to their adjacent numbers (if they exist).

For example if you want to convert the numbers 7 8 9 6 to even numbers, you can do this:
  • Choose x2, then you have: 8 9 10 6.
  • Choose x4, then you have: 8 9 11 7.
  • Choose x3, then you have: 8 10 12 8.
Find the minimum number of operations you have to do to convert all integers to odd numbers and to even numbers.
All odd, all even is a game that consists in convert all the integers x1, x2, x3,…, xN to odd numbers or to even numbers. To do this, the only operation you are allowed to do is to choose an integer xK and add 1 to xK and to their adjacent numbers (if they exist).

For example if you want to convert the numbers 7 8 9 6 to even numbers, you can do this:
  • Choose x2, then you have: 8 9 10 6.
  • Choose x4, then you have: 8 9 11 7.
  • Choose x3, then you have: 8 10 12 8.
Find the minimum number of operations you have to do to convert all integers to odd numbers and to even numbers.
All odd, all even is a game that consists in convert all the integers x1, x2, x3,…, xN to odd numbers or to even numbers. To do this, the only operation you are allowed to do is to choose an integer xK and add 1 to xK and to their adjacent numbers (if they exist).

For example if you want to convert the numbers 7 8 9 6 to even numbers, you can do this:
  • Choose x2, then you have: 8 9 10 6.
  • Choose x4, then you have: 8 9 11 7.
  • Choose x3, then you have: 8 10 12 8.
Find the minimum number of operations you have to do to convert all integers to odd numbers and to even numbers.

Input specification

The first line contain a integer number 1 <= N <= 10^6.
The second line contains N positive integers numbers xK < 2^31.
The first line contain a integer number 1 <= N <= 10^6.
The second line contains N positive integers numbers xK < 2^31.
The first line contain a integer number 1 <= N <= 10^6.
The second line contains N positive integers numbers xK < 2^31.

Output specification

Print two lines. The first one contain a integer representing the minimum number of operations that you have to do to convert all integers to odd numbers, or -1 if it is impossible. The last one contain a integer representing the minimum number of operations that you have to do to convert all integers to even numbers, or -1 if it is impossible.
Print two lines. The first one contain a integer representing the minimum number of operations that you have to do to convert all integers to odd numbers, or -1 if it is impossible. The last one contain a integer representing the minimum number of operations that you have to do to convert all integers to even numbers, or -1 if it is impossible.
The first line contain a integer number 1 <= N <= 10^6.
The second line contains N positive integers numbers xK < 2^31.

Sample input

4
7 8 9 6

Sample output

3
3

Hint(s)