Problem Brief

Maximize Beauty 🐱

FULLTIMEOA

The beauty of an array of length m is defined as the number of integers i (1 ≤ i ≤ m) such that a[i] = i.

Given an array arr of n integers, the following operation can be performed on the array while its length is greater than 1:

Choose some i (1 ≤ i ≤ length of the array) and delete arr[i] without changing the order of the remaining elements.

Find the maximum possible beauty of the array after performing this operation any number of times.

Function Description

Complete the function maximizeBeauty in the editor below.

maximizeBeauty has the following parameter:

int arr[n]: the given array

Returns

int: the maximum possible beauty of the array

1Example 1

Input

arr = [1, 3, 2, 5, 4, 5, 3]

Output

Explanation

One optimal sequence of operations is shown.

Choose i = 2, delete arr[2] = 3; arr = [1, 2, 5, 4, 5].

Choose i = 6, delete arr[6] = 3; arr = [1, 2, 5, 4, 5]

The beauty of arr is 4 since arr[1] = 1, arr[2] = 2, arr[4] = 4, and arr[5] = 5. Return 4. Note that there can be more than one final array with maximum beauty, like [1, 2, 5, 4, 5, 3] in this case.

2Example 2

Input

arr = [6, 3, 2, 4, 3, 4]

Output

Explanation

One optimal sequence of operations is shown.

Choose i = 2, delete arr[2] = 3; arr = [6, 2, 4, 3, 4].

Choose i = 3, delete arr[3] = 4; arr = [6, 2, 3, 4].

arr[2] = 2, arr[3] = 3, and arr[4] = 4. The maximum possible beauty of the array is 3. Note that there can be more than one final arr with max beauty, like [1, 2, 5, 4, 5, 3] in this case.

3Example 3

Input

arr = [1, 3, 2, 5, 4, 5, 3]

Output

Explanation

One optimal sequence of operations is shown.

Choose i = 2, delete arr[2] = 3; arr = [1, 2, 5, 4, 5, 3]

Choose i = 6, delete arr[6] = 3; arr = [1, 2, 5, 4, 5]

The beauty of arr is 4 since arr[1] = 1, arr[2] = 2, arr[4] = 4, and arr[5] = 5. Return 4.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ n ≤ 2000

1 ≤ arr[i] ≤ 10⁵