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 JAVA):

Solution:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int N, M;
	static ArrayList<ArrayList<Integer>> bar = new ArrayList<ArrayList<Integer>>();
	static HashSet<State> used = new HashSet<State>();
	static int[] goal;

	public static void main(String[] args) {
		N = sc.nextInt();
		M = sc.nextInt();
		goal = new int[N];
		for (int i = 0; i < N - 1; ++i) {
			bar.add(new ArrayList<Integer>());
			goal[i + 1] = i + 1;
		}
		for (int i = 0; i < M; ++i) {
			int a = sc.nextInt() - 1;
			bar.get(a).add(i);
			int tmp = goal[a];
			goal[a] = goal[a + 1];
			goal[a + 1] = tmp;
		}
		HashSet<State> cur = new HashSet<State>();
		cur.add(new State());
		for (int i = 0;; ++i) {
			HashSet<State> next = new HashSet<State>();
			for (State s : cur) {
				if (s.goal()) {
					System.out.println(i);
					return;
				}
				s.trans(next, 0, 0);
			}
			cur = next;
		}
	}

	static class State {
		int[] count;
		int[] match;

		State() {
			count = new int[N - 1];
			match = new int[N];
			for (int i = 0; i < N; ++i) {
				match[i] = i;
			}
		}

		State(State o) {
			count = o.count.clone();
			match = o.match.clone();
		}

		public int hashCode() {
			return Arrays.hashCode(count) * 31 ^ Arrays.hashCode(match);
		}

		public boolean equals(Object o) {
			if (this == o) return true;
			if (getClass() != o.getClass()) return false;
			return Arrays.equals(count, ((State) o).count) && Arrays.equals(match, ((State) o).match);
		}

		void trans(HashSet<State> next, int use, int pos) {
			if (pos == N - 1) {
				if (use == 0) return;
				State n = new State(this);
				for (int i = 0; i < N - 1; ++i) {
					if ((use & (1 << i)) != 0) {
						n.count[i]++;
						int tmp = n.match[i];
						n.match[i] = n.match[i + 1];
						n.match[i + 1] = tmp;
					}
				}
				if (!used.contains(n)) {
					used.add(n);
					next.add(n);
				}
				return;
			}
			trans(next, use, pos + 1);
			if (canUse(use, pos)) {
				trans(next, use | (1 << pos), pos + 1);
			}
		}

		boolean canUse(int use, int pos) {
			if (count[pos] == bar.get(pos).size()) return false;
			if (pos > 0 && (use & (1 << (pos - 1))) != 0) return false;
			//			if (pos > 0) {
			//				if (count[pos - 1] < bar.get(pos - 1).size()
			//						&& bar.get(pos - 1).get(count[pos - 1]) < bar.get(pos).get(count[pos])) return false;
			//			}
			//			if (pos < N - 2) {
			//				if (count[pos + 1] < bar.get(pos + 1).size()
			//						&& bar.get(pos + 1).get(count[pos + 1]) < bar.get(pos).get(count[pos])) return false;
			//			}
			return true;
		}

		boolean goal() {
			for (int i = 0; i < N - 1; ++i) {
				if (count[i] != bar.get(i).size()) return false;
				if (match[i] != goal[i]) return false;
			}
			return true;
		}
	}

}