시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 107 49 39 46.429%

문제

택희는 이번 대회에 사용하기 위해 그래프를 몇 개 만들었다.

택희의 그래프 데이터는 항상 아래의 형식을 따른다.

N M U1 V1 U2 V2 U3 V3 ... UM VM

위는 정점이 N개, 간선이 M개인 그래프 데이터로, 모든 Ui, Vi에 대해 1 ≤ Ui, Vi ≤ N을 만족하며, NM 뒤에 등장하는 간선 정보(U, V 페어)는 정확히 M개이다. 그 외의 다른 조건은 없다.

택희는 대회에 사용할 모든 그래프를 만들었고, 데이터를 업로드하려던 그 순간! 갑자기 영훈이가 나타나 데이터의 여기저기에 임의의 정수를 몇 개 써 넣어 버렸고, 택희는 순간적인 상황 변화를 받아들이지 못하고 격한 욕설을 내뱉으며 영훈이에게 당장 원래 데이터로 고쳐 두라고 말한 뒤 자리를 떠나 버렸다.

영훈이는 최대한 빠르게 그래프 데이터를 복원해야 한다. 하지만 자신이 어디에 어떤 수를 썼는지 전혀 기억하지 못하는 영훈이는 고민에 빠졌다.

영훈이는 자신이 데이터에 한 일은 수를 임의의 위치에 넣은 것뿐이라는 것을 알기에, 데이터에서 몇 개의 수를 지워 그래프 데이터를 만들려 한다. 즉, 수들의 원래 순서를 유지하면서 수 일부를 지워, 남은 수들이 '올바른 데이터' 가 되도록 하려는 것이다. 이때 '올바른 데이터' 란,

  • 4개 이상의 정수로 이루어져 있고,
  • 택희가 처음 만든 데이터의 형식을 따르며,
  • 택희가 지키려 했던 모든 조건을 지키고 있는 데이터를 의미한다.

영훈이는 그래프를 복원할 방법이 여러 가지라면 기왕이면 노드의 수(N)가 가장 큰 것을, 그러한 것도 여러 가지라면 간선의 수(M)가 가장 큰 것을 복원할 것이다.

현재 데이터의 상태가 주어졌을 때, 영훈이가 복원할 그래프의 노드의 수와 간선의 수를 알아내보도록 하자.

입력

첫째 줄에 데이터에 기록되어 있는 정수의 개수 K가 주어진다. (4 ≤ K ≤ 200,000)

이어 둘째 줄에 데이터에 기록된 수 a1, a2, ..., ak가 순서대로 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 200,000)

출력

영훈이가 복원할 그래프의 노드의 수 N과 간선의 수 M을 공백으로 구분하여 출력한다.

그러한 것이 여러 가지라면 N이 가장 큰 것을, 그런 것도 여러 가지라면 M이 가장 큰 것을 골라야 한다.

만약 수를 어떻게 지우더라도 올바른 데이터를 만들 수 없다면 첫째 줄에 -1 하나만을 출력한다.

예제 입력 1

4
2 1 1 1

예제 출력 1

2 1

영훈이가 아무 수도 지우지 않으면 아래와 같은 그래프를 만들 수 있다.

예제 입력 2

12
5 5 2 9 8 2 6 12 8 1 5 14

예제 출력 2

9 2

5 5 2 9 8 2 6 12 8 1 5 14

위와 같이 정점이 9개, 간선이 2개인 그래프를 만들 수 있다.

예제 입력 3

4
1 2 3 4

예제 출력 3

-1