Overview

We want to find the number of contiguous intervals containing all \(7\) types of stamps. By sweeping the right endpoint of the interval, we count the number of valid left endpoints that satisfy the condition based on the last occurrence of each type.

Analysis

Checking All Intervals is Too Slow

There are \(\frac{N(N+1)}{2}\) intervals \((l,r)\) in total. Any approach that checks every interval will take \(O(N^2)\) time even if checking each condition is accelerated, which is too slow for \(N \le 10^6\).

Therefore, we consider: for a fixed right endpoint \(r\), how many valid left endpoints \(l\) satisfy the condition? We can count them collectively.

Focusing on the “Last Occurrence” of Each Type

Considering checkpoints \(1\) through \(r\), let \(\mathrm{last}[k]\) be the position where stamp type \(k\) last appeared. For types that have not appeared yet, let this value be \(0\).

The necessary and sufficient condition for interval \([l,r]\) to contain type \(k\) is:

\(l \le \mathrm{last}[k]\)

If the last occurrence is at or after \(l\), that stamp can be collected within the interval; if it is before \(l\), it does not exist in the interval.

Therefore, the condition for all \(7\) types to be included is:

\(l \le \min_{1 \le k \le 7}\mathrm{last}[k]\)

If we let this minimum value be \(m\), the valid left endpoints are \(1,2,\dots,m\), which gives \(m\) endpoints in total.

If there is any type that has not appeared yet, \(m=0\), so the case where there are no valid intervals is handled by the same formula.

Example

Consider the following sequence of stamps:

\(1,2,3,4,5,6,7,1\)

When the right endpoint is \(r=7\), the last occurrences of each type are:

\((1,2,3,4,5,6,7)\)

The minimum value is \(1\), so the only valid left endpoint is \(l=1\).

Advancing the right endpoint to \(r=8\), the last occurrence of type \(1\) is updated to:

\((8,2,3,4,5,6,7)\)

The minimum value is now \(2\), so there are \(2\) valid left endpoints: \(l=1,2\).

In this way, by adding the minimum value to the answer for each right endpoint, we can count all valid intervals without duplicates or omissions.

Algorithm

In the code, stamp types \(1,\dots,7\) correspond to indices \(0,\dots,6\).

1. Initialize an array last, which stores the last occurrence of each type, with all \(0\)s.
2. Initialize minimum (representing the minimum value of last) and answer to \(0\).
3. Iterate the right endpoint \(i\) from \(1\) to \(N\):
   • Let c be the index corresponding to the current type.
   • Save the value of last[c] before updating into previous.
   • Update last[c] to the current position \(i\).
   • Update minimum if necessary.
   • Add minimum to answer.
4. Output answer.

When to Recalculate the Minimum

Computing min(last) every time is fast enough because there are only \(7\) elements. The provided code further avoids unnecessary recalculations.

Updating last[c] always strictly increases its value.

• When previous > minimum:
  Since this only increases an element that is not the minimum, the minimum value does not change.
• When previous == minimum:
  Since the element that attained the minimum has changed, recalculate min(last).

This ensures that minimum is always maintained as the minimum value of last. Since the correct number of intervals is added for each right endpoint, the final answer will be the desired total.

Complexity

• Time complexity: \(O(7N)=O(N)\)
  At each checkpoint, we find the minimum of an array of length at most \(7\).
• Space complexity: Auxiliary space for the algorithm is \(O(7)=O(1)\).
  However, since the provided code loads the entire input at once using read().split(), the total memory including input data is \(O(N)\).

Implementation Notes

• Use 1-based indexing for checkpoint positions.
  This allows \(0\) to represent unvisited types, and the minimum occurrence position directly equals the number of valid left endpoints.

• Save the value before updating.
  To determine whether recalculating the minimum is necessary, save last[c] into previous before overwriting it.

• Be mindful of integer types for the answer.
  The answer can be at most \(\frac{N(N+1)}{2}\), which may overflow a 32-bit integer. Python handles arbitrarily large integers automatically, but in languages like C++, a 64-bit integer type (such as long long) is required.

  Source Code

import sys


def main():
    tokens = iter(sys.stdin.buffer.read().split())
    n = int(next(tokens))

    last = [0] * 7
    answer = 0
    minimum = 0

    for i in range(1, n + 1):
        c = int(next(tokens)) - 1
        previous = last[c]
        last[c] = i
        if previous == minimum:
            minimum = min(last)
        answer += minimum

    print(answer)


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-6-astra-medium.