Maximum Distinct Features over a Continuous Time Period

You are given a list of user interactions, where each interaction is recorded by a timestamp and a feature identifier. A continuous time period is defined as a sequence of days (timestamps) with no gaps, i.e. if a period starts at day \(t\) and ends at day \(t+k\), then every day between \(t\) and \(t+k\) (inclusive) appears in the records. In each day, multiple interactions may occur, and they are all considered when forming the union of features for that day.

Your task is to determine the maximum number of distinct feature IDs that occur in the union of interactions over any continuous period of time.

Note: The interactions are not necessarily given grouped by day. You must group the interactions by their timestamps, then consider only blocks of consecutive timestamps.

For example, consider the following interactions:

Timestamp Feature
1         2
1         3
2         2
3         4
3         2
4         5

Grouping by timestamp:

• Day 1: {2, 3}
• Day 2: {2}
• Day 3: {2, 4}
• Day 4: {5}

The continuous period from day 1 to day 4 has a union of \(\{2,3,4,5\}\) making the answer 4.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(N\) representing the number of interactions. This is followed by \(N\) lines, each containing two integers separated by a space: the timestamp and the feature_id.

outputFormat

The output is a single integer written to standard output (stdout): the maximum number of distinct feature IDs over any continuous (consecutive) period of time.

## sample

6
1 2
1 3
2 2
3 4
3 2
4 5

4