망가진 데이터

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

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

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

이는 정점이 N개, 간선이 M개인 그래프 데이터로, 모든 Ui, Vi에 대해 1 ≤ Ui, Vi ≤ N을 만족하고, N과 M 뒤에 나오는 간선 정보(U, V 쌍)는 정확히 M개다. 그 밖의 조건은 없다.

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

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

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

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

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

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

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

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

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

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

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