title: Maximize the sum of product of adjacent numbers
body: <p>Here is a question that I encountered during an <a href="http://interviewstreet.com" rel="nofollow">Interviewstreet</a> <a href="https://zulily.interviewstreet.com/" rel="nofollow">codesprint</a>.
  I was unable to find a a solution or even think in its direction. I'd be thankful if someone could help me find the soultion, or explain me how the problem neeeds to be dealt with.</p>
  
  <blockquote>
    <p>Given numbers 1, 2, 3, .., N,  arrange them in a order such that the
    sum of product of adjecent numbers is maximized.</p>
    
    <p>For example: if N = 3, and we order them as ( 1, 2, 3 ), the sum of
    products is 1*2 + 2*3  = 8 and if we order them as ( 1, 3 ,2 ) the sum
    of products is 1*3 + 3*2 = 9.</p>
    
    <p><strong>Input format :</strong></p>
    
    <p>First line of the input contains T, the number of test-cases. Then
    follow T lines, each containing an integer N.</p>
    
    <p><strong>Output format :</strong></p>
    
    <p>For each test case print the maximum sum of product of adjacent
    numbers.</p>
    
    <p><strong>Sample input :</strong></p>
    
    <p>2 2 4</p>
    
    <p><strong>Sample output :</strong></p>
    
    <p>2 23</p>
    
    <p><strong>Explanation :</strong></p>
    
    <p>In first test case given permutation is ( 1, 2 ). So maximum sum of
    product is 1*2. In Second test case the numbers are (1,2,3,4).
    Arrangement 1,3,4,2 has sum of product of adjacent numbers as
    1*3+3*4+4*2 = 23. No other arrange has sum of product of adjacent
    numbers more than 23.</p>
    
    <p><strong>Constraints :</strong></p>
    
    <p>1 &lt;= T &lt;= 10 1 &lt;= N &lt;= 200000</p>
  </blockquote>