#include<iostream>
#include<algorithm>
#include<vector>
#define BIT(x) (1<<(x))
using namespace std;
int ans;
vector<int> o_line;
int main(){
    int N, M;
    cin>>N>>M;
    vector<int> side(M);
    ans = M;
    o_line.resize(N);
    for(int i=0;i<N;++i){
        o_line[i] = i;
    }
    for(int i=0;i<M;++i){
        cin >> side[i];
        --side[i];
        swap(o_line[side[i]], o_line[side[i]+1]);
    }
    vector<int> use(M);
    for(int i=0;i<M;++i){
        use[i] = i;
    }
    do{
        vector<int> line(N);
        for(int i=0;i<N;++i){
            line[i] = i;
        }
        for(int i=0;i<M;++i){
            swap(line[side[use[i]]], line[side[use[i]]+1]);
        }
        if(o_line == line){
            int count = 1;
            int used = 0;
            for(int i=0;i<M;++i){
                int num = side[use[i]];
                if((used & BIT(num)) || (used & BIT(num + 1))){
                    ++count;
                    used = BIT(num)*3;
                }else{
                    used += BIT(num)*3;
                }
            }
            ans = min(count, ans);
        }
    }while(next_permutation(use.begin(), use.end()));
    cout << ans << endl;
    return 0;
}

