#include <iostream>
#include <algorithm>
#include <vector>
using namespace std ;
vector<int> digs ;
const int INF = 1000000000 ;
int b, p ;
int main() {
   cin >> b >> p ;
   vector<int> cur0, cur1, nxt0, nxt1 ;
   cur0.push_back(0) ;
   cur1.push_back(INF) ;
   vector<int> x(p) ;
   for (auto &v: x)
      cin >> v ;
   reverse(x.begin(), x.end()) ;
   for (auto v: x) {
      nxt0.clear() ;
      nxt1.clear() ;
      int nxt0sz = max(cur0.size(), cur1.size()) ;
      int nxt1sz = max(cur0.size() + b - v, cur1.size() + b - v - 1) ;
      nxt0.resize(nxt0sz, INF) ;
      nxt1.resize(nxt1sz, INF) ;
      int both = min(cur0.size(), cur1.size()) - 1 ;
      if (both < 0)
         both = 0 ;
      nxt1[b - v] = cur1[0] ;
      for (int j=0; j<both; j++) {
         nxt0[j] = min(cur1[j] + v + 1, cur0[j] + v) ;
         nxt1[j + b - v] = min(cur0[j], cur1[j + 1]) ;
      }
      for (int j=both; j<(int)cur0.size(); j++) {
         nxt0[j] = min(nxt0[j], cur0[j] + v) ;
         nxt1[j + b - v] = min(nxt1[j + b - v], cur0[j]) ;
      }
      for (int j=both; j<(int)cur1.size(); j++) {
         nxt0[j] = min(nxt0[j], cur1[j] + v + 1) ;
         nxt1[j + b - v - 1] = min(nxt1[j + b - v - 1], cur1[j]) ;
      }
      swap(cur0, nxt0) ;
      swap(cur1, nxt1) ;
   }
   int r = INF ;
   for (int i=0; i<(int)cur0.size(); i++)
      r = min(r, max(i, cur0[i])) ;
   for (int i=0; i<(int)cur1.size(); i++)
      r = min(r, max(i, cur1[i])) ;
   cout << r << endl ;
}