title: Find the minimum two non edge, non adjacent entries in an array
body: <p>I had the following question</p>
  
  <p>Find the smallest two <em>nonadjacent</em> values in an array, such that non of these elements is on the array edge (no A[0] and no A[n-1])
  The runtime of the algorithm should be O(n)</p>
  
  <p>I first thought about sorting the array, but sorting would cost O(nlogn)
  Ignoring this fact for a second, if we sort the array, we can not just take the first two values, since they might violate the conditions mentioned above? and then what? take the next element and try, if not take the next, I can't see an easy solution there</p>
  
  <p>Another solution is to generate all allowed pairs and find the pair with the minimum sum. But finding all pairs cost O(n^2)</p>
  
  <p>Any ideas?</p>