E. New Year Parties

https://codeforces.com/contest/1283/problem/E

Oh, New Year. The time to gather all your friends and reflect on the heartwarming events of the past year...

nn friends live in a city which can be represented as a number line. The ii-th friend lives in a house with an integer coordinate xixi. The ii-th friend can come celebrate the New Year to the house with coordinate xi−1xi−1, xi+1xi+1 or stay at xixi. Each friend is allowed to move no more than once.

For all friends 1≤xi≤n1≤xi≤n holds, however, they can come to houses with coordinates 00 and n+1n+1 (if their houses are at 11 or nn, respectively).

For example, let the initial positions be x=[1,2,4,4]x=[1,2,4,4]. The final ones then can be [1,3,3,4][1,3,3,4], [0,2,3,3][0,2,3,3], [2,2,5,5][2,2,5,5], [2,1,3,5][2,1,3,5] and so on. The number of occupied houses is the number of distinct positions among the final ones.

So all friends choose the moves they want to perform. After that the number of occupied houses is calculated. What is the minimum and the maximum number of occupied houses can there be?

Input

The first line contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of friends.

The second line contains nn integers x1,x2,…,xnx1,x2,…,xn (1≤xi≤n1≤xi≤n) — the coordinates of the houses of the friends.

Output

Print two integers — the minimum and the maximum possible number of occupied houses after all moves are performed.

Examples

input

Copy

4 1 2 4 4

output

Copy

2 4

input

Copy

9 1 1 8 8 8 4 4 4 4

output

Copy

3 8

input

Copy

7 4 3 7 1 4 3 3

output

Copy

3 6

Note

In the first example friends can go to [2,2,3,3][2,2,3,3]. So friend 11 goes to x1+1x1+1, friend 22 stays at his house x2x2, friend 33 goes to x3−1x3−1 and friend 44 goes to x4−1x4−1. [1,1,3,3][1,1,3,3], [2,2,3,3][2,2,3,3] or [2,2,4,4][2,2,4,4] are also all valid options to obtain 22 occupied houses.

For the maximum number of occupied houses friends can go to [1,2,3,4][1,2,3,4] or to [0,2,4,5][0,2,4,5], for example.

---

思路：先说一下第一眼的想法。dp。然后就动手去写了。写完发现样例二和样例三的最大值不对..也不知道错哪儿了。翻了翻题解是个贪心。

先考虑最小值，如果说有一段连续的值，不管其中每个值的出现次数是多少，这一段连续的肯定是能放到一个屋子里的。

比如2 2 2 2 3 3 3 4 4 4 4。以2为首可以将4给包括进来放到一间屋子里（2->3<-4)

模拟即可。

考虑最大值。

尽量让所有人都往无人的坐标跑，从而达到最大值。

如果当前点无人就跳过。

如果当前点人数为1的话就尽量往左边一格的空位走。这一种决策不会使结果变坏。比如0 1 0，往左走一个1 0 0 不会让结果变少。 0 1 2的时候可以变成1 1 1更优

如果当前点人数为>=2的话除了考虑左边一格子是否无人，还要判断右边一个格子。如果左边空的并且走过去一个人后这个点人数仍然>=2。那么往右走是不会让结果变坏的。

比如 1 2 1 1,变成2 1 1 1,没有影响。

比如 1 2 1 0的时候往右移动一个能最终变成1 1 1 1.更优。

---

顺便附上dp的代码。(不知道为啥是错的，样例过不去

f[i][0/1/2]:共有i个点且第i个点的人去走左边/不走 /去右边的最少/最大房间数。

然后讨论当前点的坐标和上一个点的左边的距离长度。

#include<iostream> #include<vector> #include<queue> #include<cstring> #include<cmath> #include<map> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; const int maxn=2e5+100; typedef long long LL; LL f1[maxn][3],f2[maxn][3]; LL a[maxn]; LL ans1=0x3f3f3f3f;LL ans2=0; LL fmin(LL a,LL b,LL c) { return min(a,min(b,c)); } LL fmax(LL a,LL b,LL c) { return max(a,max(b,c)); } int main(void) { cin.tie(0);std::ios::sync_with_stdio(false); LL n;cin>>n; for(LL i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); memset(f1,0x3f,sizeof(f1)); f1[1][0]=f1[1][1]=f1[1][2]=1; //注意a[n]==n的时候可以往右n+1转移 //注意a[1]==1的时候可以a[1]往0转移 //转移最小 for(LL i=2;i<=n;i++) { if(a[i]-a[i-1]>=3) { for(LL j=0;j<=2;j++){ f1[i][j]=1+fmin(f1[i-1][0],f1[i-1][1],f1[i-1][2]); } } else if(a[i]-a[i-1]==2) { f1[i][0]=fmin(f1[i-1][0]+1,f1[i-1][1]+1,f1[i-1][2]); f1[i][1]=1+fmin(f1[i-1][0],f1[i-1][1],f1[i-1][2]); f1[i][2]=1+fmin(f1[i-1][0],f1[i-1][1],f1[i-1][2]); } else if(a[i]-a[i-1]==1) { f1[i][0]=fmin(f1[i-1][0]+1,f1[i-1][1],f1[i-1][2]+1); f1[i][1]=fmin(f1[i-1][0]+1,f1[i-1][1]+1,f1[i-1][2]); f1[i][2]=1+fmin(f1[i-1][0],f1[i-1][1],f1[i-1][2]); } else if(a[i]==a[i-1]) { f1[i][0]=fmin(f1[i-1][0],f1[i-1][1]+1,f1[i-1][2]+1); f1[i][1]=fmin(f1[i-1][0]+1,f1[i-1][1],f1[i-1][2]+1); f1[i][2]=fmin(f1[i-1][0]+1,f1[i-1][1]+1,f1[i-1][2]); } } //转移最大 f2[1][0]=f2[1][1]=f2[1][2]=1; for(LL i=2;i<=n;i++) { if(a[i]-a[i-1]>=3) { for(LL j=0;j<=2;j++) f2[i][j]=fmax(f2[i-1][0],f2[i-1][1],f2[i-1][2])+1; } else if(a[i]-a[i-1]==2) { f2[i][0]=fmax(f2[i-1][0]+1,f2[i-1][1]+1,f2[i-1][2]); f2[i][1]=fmax(f2[i-1][0],f2[i-1][1],f2[i-1][2])+1; f2[i][2]=fmax(f2[i-1][0],f2[i-1][1],f2[i-1][2])+1; } else if(a[i]-a[i-1]==1) { f2[i][0]=fmax(f2[i-1][0]+1,f2[i-1][1],f2[i-1][2]+1); f2[i][1]=fmax(f2[i-1][0]+1,f2[i-1][1]+1,f2[i-1][2]); f2[i][2]=1+fmax(f2[i-1][0],f2[i-1][1],f2[i-1][2]); } else if(a[i]==a[i-1]) { f2[i][0]=fmax(f2[i-1][0],f2[i-1][1]+1,f2[i-1][2]+1); f2[i][0]=fmax(f2[i-1][0]+1,f2[i-1][1],f2[i-1][2]+1); f2[i][0]=fmax(f2[i-1][0]+1,f2[i-1][1]+1,f2[i-1][2]); } } cout<<fmin(f1[n][0],f1[n][1],f1[n][2])<<" "<<fmax(f2[n][0],f2[n][1],f2[n][2])<<endl; return 0; }