class Solution {
    public int solution(int[] A) {
        // Find index of all peaks
        HashSet<Integer> peak_indexes = new HashSet<Integer>();
        for (int i = 1; i < A.length - 1; i++) {
            int left = A[i - 1];
            int center = A[i];
            int right = A[i + 1];
            if (left < center && center > right) {
                peak_indexes.add(i);
            }
        }

        int len = A.length;
        int max_blocks = len / 3;
        int blocks = 1;
        int max_num_blocks = 0;
        while(blocks <= max_blocks) {
            if (len % blocks == 0) {
                int block_size = len / blocks;
                boolean valid = true;
                for (int i = 0; i <= len - block_size; i += block_size) {
                    boolean block_valid = false;
                    for (int j = i; j < i + block_size; j++) {
                        if (peak_indexes.contains(j)) {
                            block_valid = true;
                            break;
                        }
                    }
                    if (!block_valid) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    max_num_blocks = blocks;
                }
            }
            blocks++;
        }

        return max_num_blocks;
    }

}

A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

A[0], A[1], ..., A[K − 1],
    A[K], A[K + 1], ..., A[2K − 1],
    ...
    A[N − K], A[N − K + 1], ..., A[N − 1].

one block (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). This block contains three peaks.
    two blocks (1, 2, 3, 4, 3, 4) and (1, 2, 3, 4, 6, 2). Every block has a peak.
    three blocks (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). Every block has a peak. Notice in particular that the first block (1, 2, 3, 4) has a peak at A[3], because A[2] < A[3] > A[4], even though A[4] is in the adjacent block.

class Solution { public int solution(int[] A); }

A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

N is an integer within the range [1..100,000];
    each element of array A is an integer within the range [0..1,000,000,000].

expected worst-case time complexity is O(N*log(log(N)));
    expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).