title: O(N*log(log(N))) algorithm for Codility's Peaks?
body: <p>The task description is here: <a href="https://codility.com/demo/take-sample-test/peaks" rel="nofollow noreferrer">https://codility.com/demo/take-sample-test/peaks</a>
  It's also here: <a href="https://stackoverflow.com/questions/20886486/codility-peaks-complexity">Codility Peaks Complexity</a></p>
  
  <p>First, I tried solving this myself but was only able to come up with what I believed to be a brute force solution. However, it scored 100/100: <a href="https://codility.com/demo/results/demoRNWC3P-X4U" rel="nofollow noreferrer">https://codility.com/demo/results/demoRNWC3P-X4U</a></p>
  
  <p>Which obviously is completely unsatisfying for me. ;) The outer loop is called for each factor of <code>N</code> (or for each peak, whichever is smaller) and the inner one is called for each peak (just checking if there's a peak in every block). Maybe that's <code>O(N^2)</code>, maybe a bit better (since it passes the tests in time limits) but I'm almost sure it's not <code>O(N*log(log(N)))</code>.</p>
  
  <p>Then I tried searching for an <code>O(N*log(log(N)))</code> solution but everyone else seems to have a pretty similar solution to mine.</p>
  
  <p>So does anyone have an idea for an <code>O(N*log(log(N)))</code> <strong>(or a better one)</strong> solution?</p>
  
  <p><em>Also, if anyone could tell me what complexity my solution has I'd be grateful.</em></p>