Uniqueness

Time limit: 1 s.
Memory limit: 256 MB

You are given an array of \(n\) integers.

A segment of the array is called distinct if all elements inside it are pairwise different.

Your task is to find the maximum possible length of a contiguous distinct segment.

In other words, find the largest value of \(r-l+1\) such that all numbers \(a_l, a_{l+1}, \ldots, a_r\) are distinct.

Input

The first line contains two integers \(n\) and \(s\) \((1 \le n \le 2 \cdot 10^5)\), where:

  • \(n\) is the number of elements in the array.
  • \(s\) is the subtask number.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\).

Output

Print a single integer: the maximum length of a contiguous segment whose elements are all distinct.

Scoring

The task consists of several subtasks. Each subtask has additional constraints and is worth a specific number of points.

Subtask Additional constraints Points
\(1\) All values are distinct. \(3\)
\(2\) \(n \le 200\). \(7\)
\(3\) \(n \le 2000\). \(8\)
\(4\) \(1 \le a_i \le 100\). \(7\)
\(5\) \(1 \le a_i \le 1000000\). \(11\)
\(6\) The answer is at least \(n-1\). \(8\)
\(7\) The array is nondecreasing. \(13\)
\(8\) There is at most one value that appears more than once. \(18\)
\(9\) No additional constraints. \(25\)

The total score is \(100\) points.

Example

Input

8 9
1 2 1 3 4 2 3 5

Output

4

Note

In the sample, one valid distinct segment is from position \(3\) to position \(6\):

1, 3, 4, 2

All elements in this segment are different, and its length is \(4\).

It can be shown that there is no distinct contiguous segment of length \(5\) or more.

Therefore, the answer is \(4\).

Solution

Maintain a sliding window containing distinct values. For every right endpoint, remember the last position where its value occurred. If that position is inside the current window, move the left endpoint past it.

Each position enters and leaves the window once. The expected complexity is \(O(N)\) time with a hash map and \(O(N)\) memory. The subtask number \(s\) does not affect the algorithm.

#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, subtask;
    cin >> n >> subtask;

    unordered_map<long long, int> lastPosition;
    int left = 0;
    int answer = 0;

    for (int right = 0; right < n; right++) {
        long long value;
        cin >> value;

        auto it = lastPosition.find(value);
        if (it != lastPosition.end()) {
            left = max(left, it->second + 1);
        }

        lastPosition[value] = right;
        answer = max(answer, right - left + 1);
    }

    cout << answer << '\n';
}