Poor Computer

Brian Fulk는 며칠째 정말 형편없는 컴퓨터와 씨름하고 있다. 지금 그는 양의 정수 $x$를 입력받아 그 배수 몇 개, 예를 들어 $a_1 x, \ldots, a_N x$를 반환하는 아주 간단한 프로그램을 작성하려 한다. 하지만 이 컴퓨터에는 덧셈, 뺄셈, 왼쪽 시프트라는 세 가지 산술 연산만 있어서 이런 간단한 작업조차 쉽지 않다.

상황을 더 자세히 설명하자. 처음에 컴퓨터에는 주어진 양의 정수 $x$만 저장되어 있다. Brian이 작성하는 프로그램은 주어진 승수 $a_1, \ldots, a_N$에 대해 $a_1 x, \ldots, a_N x$를 다음 연산만 사용해 만들어야 한다.

• 두 값의 덧셈,
• 두 값의 뺄셈,
• 비트 왼쪽 시프트($n$비트 왼쪽 시프트는 $2^n$을 곱하는 것과 같다).

프로그램은 $42x$보다 큰 값을 만들어서는 안 되며, 이 제약 아래에서는 오버플로가 일어나지 않는다고 가정할 수 있다. 또한 이 컴퓨터는 음수를 표현할 수 없으므로 작은 값에서 큰 값을 빼는 뺄셈이 있어서는 안 된다.

42라는 숫자가 어디서 나왔는지 궁금해하는 사람도 있을 것이다. 생명, 우주, 그리고 모든 것에 대한 답과 관련된 깊은 이유가 있지만, 그것을 설명할 공간과 시간이 부족하다.

여러분의 과제는 배수 $a_1 x, \ldots, a_N x$를 만들어 내는 가장 짧은 연산 순서를 찾아 그 길이를 보고하는 프로그램을 작성하는 것이다. 이 수들은 어떤 순서로 만들어져도 된다.

다음은 첫 번째 샘플 입력에 대한 연산 순서의 예를 C++/Java 스타일 언어로 나타낸 것이다.

a = x << 1;  // 2x
b = x + a;   // 3x
c = a + b;   // 5x
d = c << 2;  // 20x
e = d - b;   // 18x

첫째 줄에 승수의 개수 $N$이 주어진다. 둘째 줄에 $N$개의 정수 $a_1, \ldots, a_N$이 주어지며, 각각은 $x$의 승수를 나타낸다.

$N \le 41$이고 $2 \le a_i \le 42$ $(1 \le i \le N)$라고 가정할 수 있다. 또한 $a_1, \ldots, a_N$은 모두 서로 다르다.

값 $a_1 x, \ldots, a_N x$를 만들어 내는 데 필요한 최소 연산 횟수를 한 줄에 출력한다.