Factory Quality Control Sensor Placement

Problem Statement

A manufacturing facility has a production line with N stations arranged in sequence, indexed from 0 to N-1. Each station has a quality sensor reporting a score A[i], where all scores are non-negative integers. Segment Formation Process Segments are formed according to the following greedy process, not by enumerating all qualifying pairs. The process scans stations left to right, maintaining a deque (double-ended queue) of candidate left endpoints in strictly decreasing order of score. At each station j: Step 1: Eviction: Any candidate left endpoint i at the back of the deque with A[i] ≤ A[j] is permanently discarded. This ensures that for any candidate i, no later element with value ≥ A[i] appears before it is matched, enforcing strict local dominance. Step 2: Registration: Station j is added to the back of the deque as a new candidate left endpoint. Step 3: Matching: The front of the deque (the leftmost remaining candidate) is checked. If A[front] − A[j] ≥ D, the leftmo