Company: SAP Labs_5sep
Difficulty: medium
Aesthetically Pleasing Garden Problem Description 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 finds his trees aesthetically pleasing if they alternately increase and decrease in height (..., shorter, taller, shorter, taller, ...). Note that two adjacent trees cannot have equal heights. It may turn out that some trees have to be shortened in order to keep the look of the garden aesthetically pleasing. Jimmy is a lazy type, so he wants to put as little energy as possible into obtaining the desired look for his garden. What is the minimum number of trees that should be shortened so that Jimmy would find his garden aesthetically pleasing? Write a function: int solution(vector<int> &A); that, given an array A consisting of N integers, where A[K] denotes the height of the K-th tree, returns the minimum number of trees that s