Longest Neat Subsequence

Problem A block is an array in which every element equals the array's length — [1], [3,3,3] and [4,4,4,4] are blocks, while [1,1,1] and [2,3,3] are not. An array is neat if it can be obtained by concatenating an arbitrary number of blocks (possibly zero), so the empty array is neat. Given an array a of n integers, find the length of its longest neat subsequence.

Input / Output

• Input: an array a of n integers with 1 <= a[i] <= n
• Output: an integer — the length of the longest subsequence of a that is neat

Constraints

• 1 <= n <= 2*10^5, so enumerating subsequences is infeasible; an O(n) / O(n log n) solution is expected
• Subsequence, not subarray — elements need not be contiguous, but relative order must be preserved
• The blocks making up the answer need not be identical to one another
• The answer can be 0 — if no block can be formed at all, the empty subsequence is the only neat one

Example

• a = [2,2,1,1] → 4; the whole array is neat: [2,2] + [1] + [1]
• a = [1,2,3,3,3,1] → 5; take [1,3,3,3,1] = [1] + [3,3,3] + [1]
• a = [8,8,8,8,8,8,8,7] → 0; an 8-block needs eight 8s but only seven exist, and a lone 7 needs seven 7s
• a = [2,3,3,1,2,3,5,1,1,7] → 5