-module(peaks).
-export([peaks/1]).

peaks(A) ->
    N = length(A),
    case N =< 2 of
        true -> 0;
        false ->
            {Sum0, Dist0, Last0} = build_sums(A, N),
            LastVal = array:get(N - 2, Sum0),
            Sum1 = array:set(N - 1, LastVal, Sum0),
            case LastVal =:= 0 of
                true -> 0;
                false ->
                    Dist1 = max(Dist0, N - Last0),
                    case find_block_size(Dist1, N, Sum1) of
                        {ok, BlockSize} -> N div BlockSize;
                        not_found ->
                            FinalSize = smallest_divisor_from(Dist1, N),
                            N div FinalSize
                    end
            end
    end.

build_sums(A, N) ->
    Arr = array:from_list(A),
    Sum0 = array:new(N, {default, 0}),
    {SumF, {DistF, LastF}} = lists:foldl(fun(I, {Sum, {Dist, Last}}) ->
        SumPrev = array:get(I - 1, Sum),
        Ai = array:get(I, Arr),
        IsPeak = Ai > array:get(I - 1, Arr) andalso Ai > array:get(I + 1, Arr),
        case IsPeak of
            true -> {array:set(I, SumPrev + 1, Sum), {max(Dist, I - Last), I}};
            false -> {array:set(I, SumPrev, Sum), {Dist, Last}}
        end
    end, {Sum0, {0, -1}}, lists:seq(1, N - 2)),
    {SumF, DistF, LastF}.

find_block_size(Dist, N, Sum) ->
    find_block_size((Dist bsr 1) + 1, Dist, N, Sum).

find_block_size(I, Dist, _N, _Sum) when I >= Dist ->
    not_found;
find_block_size(I, Dist, N, Sum) ->
    case N rem I =:= 0 andalso check_blocks(I, I, N, Sum, 0) of
        true -> {ok, I};
        false -> find_block_size(I + 1, Dist, N, Sum)
    end.

check_blocks(J, _Step, N, _Sum, _Last) when J > N ->
    true;
check_blocks(J, Step, N, Sum, Last) ->
    SumJ = array:get(J - 1, Sum),
    case SumJ =< Last of
        true -> false;
        false -> check_blocks(J + Step, Step, N, Sum, SumJ)
    end.

smallest_divisor_from(Dist, N) ->
    case N rem Dist of
        0 -> Dist;
        _ -> smallest_divisor_from(Dist + 1, N)
    end.