Problem: Problem Statement

Mr. Takatsuki, who is planning to participate in the Aizu training camp, has a poor house and always tries to save as much paper as possible. She decided to play a ghost leg with other participants to decide the team for the Aizu training camp.

How to make Amidakuji for this training camp is as follows. First, write N vertical bars in parallel on the paper. Then, write the M horizontal bars in order from the top so that they are perpendicular to the vertical bars and the heights of the horizontal bars are all different. For example, the Amida of Sample Input 1 is as shown in Fig. 1.

Here, Mr. Takatsuki, a little dissatisfied expression. It's a waste of paper to write a ghost leg so vertically. You should be able to compress the height more. So, I want her to solve the problem of height compression of Amidakuji shown below.

First, the height of the Amidakuji is the value obtained by counting the horizontal bars that exist at the same height together as the height 1 and counting this to the bottom horizontal bar. Here, it is assumed that each horizontal bar can be freely moved up and down in order to perform height compression. However, it is not permissible to remove or add horizontal bars. The Amidakuji after height compression must meet the following conditions.

* The end points of the horizontal bar do not touch the end points of other horizontal bars.
* The result of tracing the Amidakuji after compression and the result of tracing the Amidakuji before compression match.



FIG. 2 is a compressed version of FIG. The "horizontal bar connecting vertical bars 1 and 2" moves to the top and becomes the same height as the "horizontal bar connecting vertical bars 4 and 5", and these two are height 1. After that, the "horizontal bar connecting the vertical bars 3 and 4" and the "horizontal bar connecting the vertical bars 2 and 3" have different heights, and the total height is 3.

<image>

Compress the height of the given Amidakuji and output the compressed height.

Constraints

* 2 <= N <= 8
* 1 <= M <= 8
* 1 <= ai <= N --1

Input

Each data set is input in the following format.


N M
a1
a2
...
aM


All inputs are integers. N indicates the number of vertical bars and M indicates the number of horizontal bars. Then, the information of the horizontal bar is input over M lines. ai indicates that the i-th horizontal bar connects the vertical bar ai and the vertical bar to the right of it. The i-th horizontal bar exists above the i + 1-th horizontal bar.

Output

Outputs the height of the compressed Amidakuji in one line.

Examples

Input

5 4
4
3
1
2


Output

3


Input

4 3
1
2
3


Output

3

Solution (in CPP):

Solution:
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;
  
int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};

class State{
public:
  int freq[8];
  vector<int> matrix;
  int height;
  State(int _freq[8],const vector<int>& _matrix,int _h){
    memcpy(freq,_freq,sizeof(int)*8);
    matrix = _matrix;
    height = _h;
  }
  bool operator<(const State& s) const{
    return height < s.height;
  }
  bool operator>(const State& s) const{
    return height > s.height;
  }
};

bool is_clear(const vector<int>& matrix,int freq[12],int W){
  for(int i=0;i<matrix.size();i++){
    if(matrix[i] != i) return false;
  }

  for(int i=0;i<W;i++){
    if(freq[i] != 0) return false;
  }
  return true;
}

bool is_valid(const vector<int>& matrix,int freq[12],int W){
  for(int i=0;i<W;i++){
    if(freq[i] < 0) return false;
  }
  return true;
}

int main(){
  int W,H;
  while(~scanf("%d %d",&W,&H)){
    vector<int> matrix;
    for(int i=0;i<W;i++){
      matrix.push_back(i);
    }
    map<string,int> dp;
    int freq[8];
    memset(freq,0,sizeof(freq));

    for(int i=0;i<H;i++){
      int line;
      scanf("%d",&line);
      line--;
      swap(matrix[line],matrix[line+1]);
      freq[line]++;
    }
    
    vector<int> patterns;
    for(int S=0;S<=(1<<(W-1)) - 1;S++){
      bool isok = true;
      for(int prohibit=2;prohibit <= W;prohibit++){
	int base = (1<<prohibit) - 1;

	for(int pos = 0; pos + prohibit <= W; pos++){
	  if((base & S) == base) {
	    isok = false;
	    break;
	  }
	  base <<= 1;
	}
      }

      for(int pos=0;pos<W;pos++){
	if(freq[pos] <= 0 && (S & (1<<pos))){
	  isok = false;
	}
      }

      if(isok){
	patterns.push_back(S);
      }
    }

    priority_queue<State,vector<State>,greater<State> > que;
    que.push(State(freq,matrix,0));

    int res = H;
    while(!que.empty()){
      State s = que.top();
      que.pop();

      if(!is_valid(s.matrix,s.freq,W)) continue;

      if(s.height >= H){
	goto found;
      }

      if(is_clear(s.matrix,s.freq,W)){
	res = s.height;
	goto found;
      }

      for(int i=0;i<patterns.size();i++){
	vector<int> next_matrix = s.matrix;
	int S = patterns[i];
	int next_freq[8];
	memcpy(next_freq,s.freq,sizeof(int)*W);
	
	for(int j=0;j<=W-1;j++){
	  if(S & (1<<j)){
	    swap(next_matrix[j],next_matrix[j+1]);
	    next_freq[j]--;
	  }
	}

	que.push(State(next_freq,next_matrix,s.height+1));
      }
    }

  found:;
    printf("%d\n",res);
  }
}