#define FOLD__SCOPE                                                          
                                                                             
#ifdef  FOLD__SCOPE  /// includes                                            
                                                                             
#include <fstream>                                                           
#include <vector>                                                            
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// typedefs                                            
                                                                             
/// stsz ― standard type size                                                
/// stsi ― standard type signed integer                                      
/// vtsi ― vector   type signed integer                                      
                                                                             
typedef  ::std::size_t           stsz;                                       
typedef  int                     stsi;                                       
typedef  ::std::vector < stsi >  vtsi;                                       
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// path                                                
                                                                             
stsi                                                                         
path_best_value                                                              
(                                                                            
  vtsi const      & A                                                        
, stsz        const i                                                        
, stsz        const j                                                        
)                                                                            
{                                                                            
  /// Compute the max value out of A[i…i+j−1].                               
  if ( (j <= i) || ( (1 + i) == j )  )                                       
  {                                                                          
    return 0;                                                                
  }                                                                          
                                                                             
  if ( (2 + i) == j  )                                                       
  {                                                                          
    return A[i] + A[1+i];                                                    
  }                                                                          
                                                                             
  stsz  s = 1 + i;                                                           
  /// Compute B[s] to be the max value out of A[i…s].                        
  /// Update b0, b1, and b2, to B[s−2], B[s−1], and B[s], respectively.      
  stsi  b0 = 0;  stsi  b1 = 0;  stsi  b2 = A[0 + i] + A[1 + i];              
  stsi  u  = 0;  stsi  v  = 0;  stsi  w  = 0;                                
                                                                             
  for ( s = 2 + i; j > s; ++ s  )                                            
  {                                                                          
    u = (A[s] + A[s-1]) + b0;  v = b2;  w = (u < v) ? v : u;                 
    b0 = b1;  b1 = b2;  b2 = w;                                              
  }                                                                          
                                                                             
  return b2;                                                                 
}                                                                            
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// cycle                                               
                                                                             
stsi                                                                         
cycle_best_value                                                             
(                                                                            
  vtsi const     & A                                                         
, stsz       const n                                                         
)                                                                            
{                                                                            
  /// Consider all the sums in which first position is used, v1 and v2, and  
  /// all the sums in which the first position is not used.                  
                                                                             
  /// v1: +, −, ?, …, ?, −, +                                                
  /// v2: +, +, −, ?, …, ?, −                                                
  /// v3: −, ?, …, ?                                                         
  stsi  v1 = (A[0] + A[n-1]) + path_best_value(A, 2, n - 2);                 
  stsi  v2 = (A[0] + A[  1]) + path_best_value(A, 3, n - 1);                 
  stsi  v3 =                   path_best_value(A, 1, n    );                 
                                                                             
  stsi  bv = ( (v1 < v2) ? ( (v2 < v3) ? v3 : v2 )                           
                         : ( (v1 < v3) ? v3 : v1 )   );                      
                                                                             
  return bv;                                                                 
}                                                                            
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// demo                                                
                                                                             
bool                                                                         
demo                                                                         
()                                                                           
{                                                                            
  #ifdef FOLD__SCOPE /// state                                               
                                                                             
  /// Demo state.                                                            
                                                                             
  vtsi  A;                                                                   
  stsz  n = 0;                                                               
  stsi  k = 0;                                                               
  #endif                                                                     
  if (true) { /// read                                                       
                                                                             
    /// Read problem instance.                                               
    /// Also aquire all space.                                               
                                                                             
    stsz  const min_n = 2;                                                   
    stsz  const max_n = 100000;                                              
    stsi  const min_v = 0;                                                   
    stsi  const max_v = 100;                                                 
                                                                             
                                                                             
    ::std::ifstream  is("oo.in");                                            
                                                                             
    stsz  m = 0;                                                             
    is >> m;                                                                 
                                                                             
    bool  ok = ( (min_n <= m) && (max_n >= m)  );                            
                                                                             
    if ( !ok  )                                                              
    {                                                                        
      /// Invalid input.                                                     
      return false;                                                          
    }                                                                        
                                                                             
    vtsi  u(m);                                                              
    stsi  x = 0;                                                             
    stsz  i = 0;                                                             
                                                                             
    for ( i = 0;  m > i; ++ i  )                                             
    {                                                                        
                                                                             
      is >> x;                                                               
                                                                             
      ok = ( (min_v <= x) && (max_v >= x)  );                                
                                                                             
      if ( ! ok  )                                                           
      {                                                                      
        /// Invalid input.                                                   
        return false;                                                        
      }                                                                      
                                                                             
      u[i] = x;                                                              
                                                                             
    }                                                                        
                                                                             
    /// All good.                                                            
    u.swap(A);                                                               
    n = m;                                                                   
                                                                             
  }                                                                          
  if (true) { /// solve                                                      
                                                                             
    /// Solve problem instance.                                              
                                                                             
    k = cycle_best_value(A, n);                                              
                                                                             
  }                                                                          
  if (true) { /// write                                                      
                                                                             
                                                                             
    /// Write the answer.                                                    
                                                                             
    ::std::ofstream  os("oo.out");                                           
    os << k << '\n';                                                         
                                                                             
  }                                                                          
                                                                             
  return true;                                                               
}                                                                            
                                                                             
#endif                                                                       
#ifdef  FOLD__SCOPE  /// main                                                
                                                                             
int                                                                          
main                                                                         
()                                                                           
{                                                                            
  int  status = 3;                                                           
                                                                             
  try                                                                        
  {                                                                          
    bool  const ok = demo();                                                 
    status = ( ok ? 0 : 1 );                                                 
  }                                                                          
  catch ( ... )                                                              
  {                                                                          
    status = 2;                                                              
  }                                                                          
                                                                             
  return status;                                                             
}                                                                            
                                                                             
#endif