A compliance audit trail records n transaction reference numbers in the exact order they were logged. On a healthy day, reference numbers strictly increase from one entry to the next. A batch-import glitch can corrupt a single contiguous run of entries in the trail; deleting exactly that run (which may be empty, meaning nothing is deleted, or may span the entire trail) is meant to restore a strictly increasing trail.
A purge window is a pair of indices (l, r) with 0 <= l <= r <= n: applying it deletes the entries at 0-indexed positions l, l+1, ..., r-1 and keeps every other entry, in its original order. Two purge windows are counted as different whenever their (l, r) pair is different -- even if they happen to delete nothing at all, or delete the exact same values.
Count how many purge windows (l, r) leave the kept reference numbers strictly increasing. A kept sequence of zero or one entries is considered strictly increasing.
n.n integers: the reference numbers a[0], a[1], ..., a[n-1].(l, r) that leave the trail strictly increasing.1 <= n <= 501 <= a[i] <= 1000Example 1
Input
5 5 3 4 6 7
Expected
8
Explanation
The full trail 5,3,4,6,7 is not strictly increasing because 5 is followed by the smaller 3. Deleting just the entry at position 0 (window (0,1)) leaves 3,4,6,7, which is increasing; deleting positions 1 and 2 (window (1,3), the values 3,4) leaves 5,6,7, which is increasing; deleting positions 1 through 3 (window (1,4), the values 3,4,6) leaves 5,7, which is increasing. Counting every such valid (l, r) pair gives 8 in total.
Example 2
Input
1 9
Expected
3
Explanation
With only one entry, the three possible purge windows are (0,0) (delete nothing, keep 9), (0,1) (delete the only entry, keep nothing), and (1,1) (delete nothing, keep 9). A sequence with zero or one entries always counts as strictly increasing, so all three windows are valid and the answer is 3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →