Sequence Reduction by Alternating Deletions

You are given a sequence of integers from \(1\) to \(n\). You are also provided with \(k\) operations. In each operation, you are to remove either all the elements in the odd positions or all the elements in the even positions from the current sequence. Note that positions are numbered starting from \(1\) and are re-indexed after every operation.

In particular:

• Operation 1: Remove all the elements at odd positions (i.e. remove the 1st, 3rd, 5th, ... elements) so that only the elements originally at even positions remain.
• Operation 2: Remove all the elements at even positions (i.e. remove the 2nd, 4th, 6th, ... elements) so that only the elements originally at odd positions remain.

After performing \(k\) operations, exactly one number remains. Your task is to compute this final number given the initial sequence and the list of operations.

inputFormat

The first line contains two integers (n) and (k) (with (n \ge 1) and (k \ge 1)), representing the length of the initial sequence and the number of operations. The second line contains (k) integers, each either 1 or 2, representing the type of operation to perform in order.

outputFormat

Output a single integer — the last remaining number after performing the (k) operations.

sample

5 2
2 1

3