Broken Data
Time limit1sMemory limit512 MB
Delete some integers from a sequence so the rest reads as N M U1 V1 ... UM VM with 1 <= Ui,Vi <= N; among all valid restorations, maximize N, then M.
- Level
Hard8 of 10
- Topics
- Implementation, Greedy, Dynamic programming, Prefix sum
- Solved
- No attempts yet
Problem
Taekhee made a few graphs to use in this contest.
Taekhee's graph data always follows the format below.
N M U1 V1 U2 V2 U3 V3 ... UM VM
This is graph data with N vertices and M edges, where 1 ≤ Ui, Vi ≤ N holds for every Ui and Vi, and the edge information (U, V pairs) that appears after N and M consists of exactly M pairs. There are no other conditions.
Taekhee made every graph for the contest and was about to upload the data. Just then, Younghoon suddenly appeared and wrote some arbitrary integers here and there in the data. Taekhee could not accept this sudden turn of events, spat out a stream of harsh curses, told Younghoon to fix the data back to its original state immediately, and left.
Younghoon must restore the graph data as quickly as possible. But he has no memory at all of where he wrote which numbers, so he is at a loss.
Younghoon knows that all he did was insert numbers at arbitrary positions, so he will delete some numbers from the data to produce graph data. That is, he will keep the original order of the numbers and delete some of them so that the remaining numbers form 'valid data'. Here 'valid data' means data that
- consists of at least 4 integers,
- follows the format of the data Taekhee originally made, and
- satisfies every condition Taekhee intended to keep.
If there are several ways to restore the graph, Younghoon restores the one with the largest number of nodes (N), and if there are several such ways, the one with the largest number of edges (M).
Given the current state of the data, find the number of nodes and the number of edges of the graph Younghoon will restore.
Input
The first line gives K, the number of integers recorded in the data. (4 ≤ K ≤ 200,000)
The second line gives the numbers a1, a2, ..., ak recorded in the data, in order, separated by spaces. (1 ≤ ai ≤ 200,000)
Output
Print the number of nodes N and the number of edges M of the graph Younghoon will restore, separated by a space.
If there are several such graphs, choose the one with the largest N; if there are still several, choose the one with the largest M.
If no matter how the numbers are deleted no valid data can be produced, print only -1 on the first line.