#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <list>
#include <algorithm>
#include <climits>
using namespace std;

inline void train() {
	   ios::sync_with_stdio(false);
	   cin.tie(0);
	   cout.tie(0);
}

inline int maxi(int a, int b) {
	return a > b ? a : b;
}

inline int mini(int a, int b) {
	return a < b ? a : b;
}

#define lch (root<<1)
#define rch ((root<<1)|1)
#define mids() int mid = (lrange[root] + rrange[root]) >> 1
#define lcall lch, maxi(l, lrange[root]), mini(mid, r)
#define rcall rch, maxi(mid+1, l), mini(rrange[root], r) 
#define incl (lrange[root] >= l && rrange[root] <= r)

constexpr int N = 1e6+4, NS = 3e6+3, INF = INT_MAX >> 1;
int lrange[NS], rrange[NS], cnt[NS], lside[NS], rside[NS];
// true: valid; false: invalid.
//int val[NS], lazy[NS];
bool val[NS], lazy[NS], has_lazy[NS];

inline void pushup(int root) {
	if (lrange[root] == rrange[root]) return;
	val[root] = val[lch] || val[rch];
	cnt[root] = cnt[lch] + cnt[rch];
	if (val[lch]) lside[root] = lside[lch];
	else if (val[rch]) lside[root] = lside[rch];
	else lside[root] = -1;
	if (val[rch]) rside[root] = rside[rch];
	else if (val[lch]) rside[root] = rside[lch];
	else rside[root] = -1;
}

inline void sync(int root) {
//	val[root]++;
//	lazy[root]++;
	if (val[root]) {
		//cnt[root] = 1;
		lside[root] = lrange[root];
		rside[root] = rrange[root];
		cnt[root] = rrange[root] - lrange[root] + 1;
	} else {
		lside[root] = rside[root] = -1;
		cnt[root] = 0;
	}
	
}

void build(int root, int l, int r) {
	if (l > r) return;
	lrange[root] = l;
	rrange[root] = r;
	if (l == r) {
		val[root] = true;
		sync(root);
		return;
	}
	mids();
	build(lch, l, mid);
	build(rch, mid+1, r);
	pushup(root);
}

inline void pushdown(int root) {
	if (lrange[root] == rrange[root]) {
		has_lazy[root] = false;
		return;
	}
	if (has_lazy[root]) {
		has_lazy[root] = false;
		has_lazy[lch] = has_lazy[rch] = true;
		val[lch] = val[rch] = lazy[root];
		sync(lch);
		sync(rch);
	}
}

void update(int root, int l, int r, bool value) {
	if (l > r) return;
	else if (incl) {
		val[root] = lazy[root] = value;
		has_lazy[root] = true;
		sync(root);
		return;
	}
	pushdown(root);
	mids();
	update(lcall, value);
	update(rcall, value);
	pushup(root);
}

int query_count(int root, int l, int r) {
	if (l > r) return 0;
	else if (incl) return cnt[root];
	pushdown(root);
	mids();
	return query_count(lcall) + query_count(rcall);
} 

// Find for >=.
int query_rightmost(int root, int l, int r, int req) {
	if (l > r) return -1;
	else if (l == r) {
		//if (!val[root]) return -1;
		if (query_count(root, l, r) != 1) return -1;
		return l;
	}
	pushdown(root);
	mids();
	if (r < mid+1 || (l >= lrange[root] && rside[lch] >= req)) {
		return query_rightmost(lcall, req);
	} else {
		return query_rightmost(rcall, req);
	}
}

int query_leftmost(int root, int l, int r, int req) {
	if (l > r) return -1;
	else if (l == r) {
		//if (!val[root]) return -1;
		if (query_count(root, l, r) != 1) return -1;
		return l;
	}
	pushdown(root);
	mids();
	/*
	if (r < mid + 1 || (l >= lrange[root] && rside[lch] > req)) {
		return query_rightmost(lcall, req);
	}
	else {
		return query_rightmost(rcall, req);
	}
	*/
	if (l > mid || (lside[rch] != -1 && lside[rch] < req)) {
		return query_leftmost(rcall, req);
	}
	else {
		return query_leftmost(lcall, req);
	}
}

int n, a[N], k;
//set<int, greater<int> > latest[N];
//set<int> farthest[N];
int latest[N], farthest[N];

inline int absx(int x) {
	return (x < 0) ? (-x) : x;
}

// [i, x]     [1, i)u(x, n]
inline int evaluate(int i, int x) {
	//return maxi(i-x+1, (x-1)+(n-i));
	int al = (i - x + 1);
	int bl = ((x - 1) + (n - i));
	int lens = al- bl;
	return absx(lens);
}

struct seg {
	int num, from, to;
	seg() {

	}
	seg(int from) : num(-1), from(from) {

	}
	seg(int num, int from) : num(num), from(from) {

	}
};

bool operator < (const seg &a, const seg &b) {
	return a.from < b.from;
}

//set<seg> sg;
//vector<seg> vs;
set<int> sg;
list<int> src[N];

bool cmp(const seg &a, const seg &b) {
	return a.to < b.to;
}

int main() {

	train();
	
	cin>>n>>k;
	build(1, 1, n);
	for (int i = 1; i <= n; i++) {
		cin>>a[i];
		if (!latest[a[i]]) latest[a[i]] = i;
		farthest[a[i]] = i;
		src[a[i]].push_back(i);
		sg.insert(i);
//		latest[a[i]].insert(i);
//		farthest[a[i]].insert(i);
	}
	/*
	for (int i = 1; i <= k; i++) {
		seg se = seg(a[i], latest[a[i]], farthest[a[i]]);
		vs.push_back(se);
	}
	sort(vs.begin(), vs.end(), cmp);
	*/
	long long pcnt = 0ll;
	int ans = INT_MAX;
	//vector<seg>::iterator vt = vs.begin();
	for (int i = 1; i < n; i++) {
		
		/*while (vt != vs.end() && vt->to <= i) {
			update(1, vt->from, vt->to, false);
			vt++;
		}*/
		if (query_count(1, i, i) != 1) {
			continue;
		}
		if (i == farthest[a[i]]) {
			for (auto &j : src[a[i]]) {
				sg.erase(j);
			}
			update(1, latest[a[i]] + 1, i, false);
		}
		
		auto finder = sg.upper_bound(i);
		int limit = 1;
		if (finder != sg.begin()) {
			finder--;
			limit = (*finder) + 1;
		}
		//if (limit == 1 && i == n) limit = 2;
		if (limit > i) continue;
		pcnt += query_count(1, limit, i);
		int expect = maxi(limit, (i + 1) - (n >> 1));		// OK Evaluated
		int far = query_rightmost(1, limit, i, expect);
		if (far != -1) {
			ans = mini(ans, evaluate(i, far));
		}
		int near = query_leftmost(1, limit, i, expect);
		if (near != -1) {
			ans = mini(ans, evaluate(i, near));
		}
		//sg.erase(seg(a[i], i, farthest[a[i]]));
	}
	
	// pcnt-1: The whole segment is considered.
	cout<<pcnt<<' '<<ans<<endl;

	return 0;
}