public class Flags {

    public int solution(int[] A) {
        int N = A.length;
        if (N < 3) {
            return 0;
        }

        int[] nextPeaks = new int[N];
        int numberOfPeaks = 0;
        int firstPeakPosition = -1;

        nextPeaks[N-1] = -1;
        for (int i = N - 2; i > 0; i--) {
            if (A[i] > A[i-1] && A[i] > A[i+1]) {
                nextPeaks[i] = i;
                numberOfPeaks++;
                firstPeakPosition = i;
            } else {
                nextPeaks[i] = nextPeaks[i+1];
            }
        }
        nextPeaks[0] = nextPeaks[1];

        if (numberOfPeaks < 2) {
            return numberOfPeaks;
        }

        int maxNumberOfFlags = (int)Math.ceil(Math.sqrt(N));
        int numberOfFlags = 1;
        while (maxNumberOfFlags > 1) {
            int flagPosition = firstPeakPosition;
            int flagCounter = 1;

            while (flagCounter <= maxNumberOfFlags) {
                int temp = flagPosition + maxNumberOfFlags;
                if ((temp >= N) || (nextPeaks[temp] == -1)) {
                    break;
                }

                flagPosition = nextPeaks[temp];
                flagCounter++;
            }

            numberOfFlags = Math.max(numberOfFlags, flagCounter);
            maxNumberOfFlags--;
        }

        return numberOfFlags;
    }
}