import std.stdio;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;

void main() {
    int N, M; scanf("%d %d\n", &N, &M);
    int[] a = new int[M];
    foreach (i; 0 .. M) { scanf("%d\n", &a[i]); }
    int[] b = new int[M];
    int Calc() {
        auto G = new bool[][](M, M);
        foreach (i; 0 .. M) {
            foreach (j; i + 1 .. M) {
                if (abs(b[i] - b[j]) <= 1) {
                    G[i][j] = true;
                }
            }
        }
        int Ans = 0;
        int dfs(int x) {
            int ret = 0;
            foreach (i; 0 .. M) {
                if (G[x][i]) {
                    ret = max(ret, dfs(i));
                }
            }
            return ret + 1;
        }
        foreach (int i; 0 .. M) {
            Ans = max(Ans, dfs(i));
        }
        version(Debug) {
            foreach (i; 0 .. M) {
                writef("%3d: ", b[i]);
                foreach (j; 0 .. M) {
                    if (G[i][j]) {
                        writef("%3d", b[j]);
                    }
                }
                writeln;
            }
        }
        return Ans;
    }

    int[] Result(int[] zs) {
        auto x = iota(0, N, 1).array;
        foreach (z; zs) {
            swap(x[z - 1], x[z]);
        }
        return x;
    }

    int Ans = M;

    void dfs(int x, bool[] used, int[] index) {
        used[x] = true;
        bool flag = false;
        index ~= x;
        foreach (i; 0 .. M) {
            if (used[i]) continue;
            flag = true;
            dfs(i, used, index);
        }
        if (!flag) {
            foreach (i; 0 .. M) {
                b[i] = a[ index[i] ];
            }
            if (Result(a) == Result(b)) {
                Ans = min(Ans, Calc);
            }
        }
        index.popBack;
        used[x] = false;
    }
    
    dfs(0, new bool[M], []);

    Ans.writeln;
}