Jimmy owns a garden in which he has planted N trees in a row. After a few years, the trees have grown up and now they have different heights.
Jimmy pays much attention to the aesthetics of his garden. He ends his trees aesthetically pleasing if they alternately increase and decrease in height (..., shorter, taller, shorter, taller, ...).
These are examples of aesthetically pleasing trees:
These are examples of trees that are not aesthetically pleasing:
Note that two adjacent trees cannot have equal heights. It may turn out that some trees have to be cut out, in order to keep the remaining trees aesthetically pleasing. However, there is a legal restriction that allows a gardener to cut out at most one tree in his possession. In how many ways can Jimmy cut out exactly one tree, so that the remaining ones are aesthetically pleasing?
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers, where A[K] denotes the height of the K-th tree, returns the number of ways of cutting out one tree, so that the remaining trees are aesthetically pleasing. If it is not possible to achieve the desired result, your function should return −1. If the trees are already aesthetically pleasing without any removal, your function should return 0.
Examples:
-
Given A = [3, 4, 5, 3, 7] your function should return 3:
- You can remove A[0] so the sequence becomes [4, 5, 3, 7];
- You can remove A[1] so the sequence becomes [3, 5, 3, 7];
- You can remove A[2] so the sequence becomes [3, 4, 3, 7].
-
Given A = [1, 2, 3, 4] your function should return −1, since there is no single tree that Jimmy can cut out that would leave the rest of the trees looking aesthetically pleasing.
-
Given A = [1, 3, 1, 2] your function should return 0, since the trees are already aesthetically pleasing and no removal is needed.
Assume that:
- N is an integer within the range [4..200];
- each element of array A is an integer within the range [1..1,000].