Array Annihilation
Amy, actively annihilating an array.
Already another algorithms assignment about arrays -- Amy has absolute aversion to them all! To avenge the amountful assignments, she activates an Array Annihilator Pledging Justice Executable, so all annoying arrays are abolished.
As the arrays are astronomically large, she agrees to only use one type of operation repeatedly. For each operation, she chooses two or more consecutive values in the array, and subtracts \(1\) from each of them.
Given an array, is it possible to make all values equal to \(0\) in some finite number of these operations?
As an example, consider the second sample input. The array can be fully annihilated in four operations: first, decrement the first two values (yielding \([1,3,3]\)), then decrement the last two values twice (yielding \([1,1,1]\)), and finally decrement the entire array once (yielding \([0,0,0]\)).
Input
- One line with an integer \(n \ (1 \le n \le 5\cdot 10^5)\), the length of the array.
- One line with \(n\) integers \(a \ (1 \le a \le 10^9)\), the values in the array.
Output
- If it is possible to make all values of the array equal to \(0\) in some finite number of operations, output
possible. - If this is not possible, output
impossible.
Examples
Sample 1
input
2
1 1
output
possible
Sample 2
input
3
2 4 3
output
possible
Sample 3
input
1
5
output
impossible
Sample 4
input
4
2 1 1 2
output
impossible
Sample 5
input
9
3 4 5 5 1 2 3 2 1
output
possible
Comments