#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

int n,m;
int a[105];

int main()
{
	scanf("%d%d",&n,&m);
	int odd1 = 0,odd2 = 0;
	for (int i = 1;i <= m;i++)
	{
		scanf("%d",&a[i]);
		if (a[i] & 1)
		{
			if (!odd1)
				odd1 = i;
			else if (!odd2)
				odd2 = i;
			else
			{
				puts("Impossible");
				return 0;
			}
		}
	}
	if (odd1)
		swap(a[odd1],a[1]);
	if (odd2)
		swap(a[odd2],a[m]);
	for (int i = 1;i <= m;i++)
		printf("%d ",a[i]);
	printf("\n");
	if (m == 1)
	{
		if (a[1] == 1)
		{
			puts("1");
			printf("1\n");
		}
		else
		{
			puts("2");
			printf("%d %d\n",a[1] - 1,1);
		}
		return 0;
	}
	printf("%d\n%d ",m - (a[m] == 1),a[1] + 1);
	for (int i = 2;i < m;i++)
		printf("%d ",a[i]);
	if (a[m] > 1)
		printf("%d",a[m] - 1);
	printf("\n");
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)

typedef pair<int, int> P;
int N;
vector<int> A;
const int MONOID = 0;
ll f(ll x, ll y) {
  return x + y;
}

void add(ll x, ll y) {
  ll i = x + N - 1;
  A.at(i) += y;
  while (i > 0) {
    i = (i-1)/2;
    A.at(i) = f(A.at(i*2+1), A.at(i*2+2));
  }
}

ll findRec(ll x, ll y, ll n, ll l, ll r) {
  if (r <= x || y <= l) return MONOID;
  if (x <= l && r <= y) return A.at(n);
  return f(
    findRec(x, y, n*2+1, l, (l+r)/2),
    findRec(x, y, n*2+2, (l+r)/2, r)
  );
}

ll find(ll x, ll y) {
  return findRec(x, y+1, 0, 0, N);
}

int main() {
  int n,q; cin >> n >> q;
  N = 1;
  while (N < n) N *= 2;
  vector<int> C(n);
  A.assign(3*n, 0);
  loop(i,0,n) cin >> C[i];

  vector<int> points[n+1];
  vector<int> prev(n+1, -1);
  loop(i,0,n) {
    int c = C[i];
    if (prev[c] != -1) {
      points[prev[c]].emplace_back(i);
    }
    prev[c] = i;
  }

  vector<P> qs[n+1];
  loop(i,0,q) {
    int l,r;cin >> l >> r;
    l--;r--;
    qs[l].emplace_back(r, i);
  }

  vector<int> ans(q, 0);
  for (int x=n-1; x>=0; x--) {
    for (auto &&y: points[x]) {
      add(y, 1);
    }
    for (auto q: qs[x]) {
      ans[q.second] = q.first-x+1-find(0, q.first);
    }
  }
  loop(i,0,q) cout << ans[i] << endl;
  return 0;
}
