Overview

Given a sequence of length \(N\) consisting of numbers from \(1\) to \(7\), this problem asks us to find the number of contiguous subsequences \([l, r]\) that contain all \(7\) distinct numbers.

Analysis

Naive Approach and Its Limitations

Let us consider a brute-force search over all pairs of intervals \([l, r]\) (\(1 \le l \le r \le N\)). There are \(\frac{N(N+1)}{2}\) possible intervals in total. Given the constraint \(N \le 10^6\), the total number of intervals is approximately \(5 \times 10^{11}\). Checking every interval will far exceed the execution time limit (resulting in TLE). Therefore, a more efficient approach is required.

Fixing the Right Endpoint

A standard technique for optimization is to consider: “For a fixed right endpoint \(r\), how many valid left endpoints \(l\) satisfy the condition?”

When the right endpoint is fixed at \(r\), what is the condition for stamp type \(k\) (\(1 \le k \le 7\)) to be included in the interval \([l, r]\)? Let \(last_k\) be the rightmost (most recent) index of stamp \(k\) at or before position \(r\). The condition is simply that \(l \le last_k\).

For all stamps \(1 \sim 7\) to be contained in the interval \([l, r]\), \(l \le last_k\) must hold for all \(k\). That is, we only need: $\(l \le \min(last_1, last_2, last_3, last_4, last_5, last_6, last_7)\)$

Example

For example, suppose the last occurrences of each stamp up to the current right endpoint \(r\) are as follows: - \(last_1 = 8, last_2 = 12, last_3 = 5, last_4 = 9, last_5 = 15, last_6 = 7, last_7 = 11\)

The minimum among these is \(last_3 = 5\). In this case, for any \(l\) satisfying \(l \le 5\) (namely, the \(5\) choices \(l = 1, 2, 3, 4, 5\)), the interval \([l, r]\) contains all stamps (if \(l \ge 6\), stamp \(3\) will not be included in the interval). Thus, letting \(m\) be this minimum value, the number of valid left endpoints \(l\) for the right endpoint \(r\) is exactly \(m\).

Note that if a stamp has not appeared yet, setting its \(last\) to \(0\) will make the minimum value \(m = 0\), which correctly handles the case where there are \(0\) valid choices for \(l\).

Algorithm

1. Initialize variables \(last_1, \dots, last_7\), which record the most recent occurrence of each stamp \(1 \sim 7\), to \(0\).
2. Initialize the answer counter ans to \(0\).
3. Iterate through \(r = 1\) to \(N\):
   • Update the most recent occurrence of stamp \(C_r\) to \(r\) (\(last_{C_r} = r\)).
   • Compute the minimum of the \(7\) most recent positions: \(m = \min(last_1, \dots, last_7)\).
   • Add \(m\) to ans.
4. Output the final value of ans.

Complexity

• Time Complexity: \(O(N)\)
  • The loop increments \(r\) from \(1\) to \(N\), running \(N\) iterations. In each step, updating the value and finding the minimum of \(7\) elements takes \(O(1)\) time. Thus, the overall time complexity is \(O(N)\), which is fast enough.
• Space Complexity: \(O(N)\)
  • Storing the input sequence \(C\) requires \(O(N)\) memory (only \(O(1)\) additional variables are used).

Implementation Notes

• Integer Overflow:

  • The total number of valid pairs can reach up to approximately \(\frac{N(N+1)}{2} \approx 5 \times 10^{11}\), which does not fit in a 32-bit integer. In languages like C++, a 64-bit integer type (long long) must be used (Python automatically handles arbitrarily large integers, so overflow is not an issue).

• Fast I/O:

  • Since the input size is large (\(N \le 10^6\)), reading the entire input at once in Python using sys.stdin.read().split() can significantly reduce the execution time.

    Source Code

import sys


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    C = [int(x) for x in input_data[1:]]

    l1 = l2 = l3 = l4 = l5 = l6 = l7 = 0
    ans = 0

    for i in range(1, N + 1):
        x = C[i - 1]
        if x == 1:
            l1 = i
        elif x == 2:
            l2 = i
        elif x == 3:
            l3 = i
        elif x == 4:
            l4 = i
        elif x == 5:
            l5 = i
        elif x == 6:
            l6 = i
        else:
            l7 = i

        m = l1
        if l2 < m:
            m = l2
        if l3 < m:
            m = l3
        if l4 < m:
            m = l4
        if l5 < m:
            m = l5
        if l6 < m:
            m = l6
        if l7 < m:
            m = l7

        ans += m

    print(ans)


if __name__ == "__main__":
    main()

---

This editorial was generated by gemini-3.8-flash-high.