Find Array Elements Uniquely Determined by Known Range Sums

An integer array A of length n is hidden from you; its positions are numbered 1 to n. You are given a list of ranges (L, R), and the sum A[L] + A[L+1] + ... + A[R] of every listed range is known. An element A[i] is recoverable if those range sums determine its value uniquely.

Return the positions of all recoverable elements.

Function Signature

def recoverable_positions(n: int, queries: list[tuple[int, int]]) -> list[int]:

queries[j] = (L, R) is the j-th range whose sum is known.

Rules

• Only the ranges are passed in, not their sums, so recoverability is defined independently of the sum values: position i is recoverable if and only if every two integer arrays of length n that have equal sums on every listed range also have equal values at position i.
• Ranges may repeat, overlap or nest.
• Return the recoverable positions in ascending order. If no position is recoverable, return [-1].
• In the original assessment, the input arrived on standard input (n and the number of ranges on the first line, then one L R pair per line) and the answer was printed as space-separated positions, or -1. Here the same data is passed in and returned directly.

Constraints

• 1 <= n <= 10^5
• 1 <= len(queries) <= 10^5
• 1 <= L <= R <= n for every range

Examples

Example 1

Input: n = 5, queries = [(1, 3), (1, 2), (4, 5), (5, 5)]
Output: [3, 4, 5]

A[3] is the sum over (1, 3) minus the sum over (1, 2). A[5] is the sum over (5, 5), and A[4] is the sum over (4, 5) minus A[5]. Only A[1] + A[2] is known, so raising A[1] by any amount and lowering A[2] by the same amount keeps every listed sum unchanged.

Example 2

Input: n = 4, queries = [(1, 2), (3, 4), (1, 4), (2, 3)]
Output: [-1]

Adding any integer t to A[1] and A[3] and subtracting t from A[2] and A[4] leaves all four listed sums unchanged, so no element is determined.

Example 3

Input: n = 1, queries = [(1, 1)]
Output: [1]

The only element is a listed range by itself.