Chains3

All problems in this problem set are about "chains": collections of nested ranges of integers. All problems are independent, but use the same definitions. Each problem statement contains the definitions it needs. If a term appears in multiple problems, the definition is always identical.

Definitions follow. The defined term is always in uppercase.

• An INTERVAL [x,y) with x <= y is the set of integers that are greater than or equal to x, and strictly less than y.
• There is only one EMPTY INTERVAL but it has multiple equivalent notations. For example, [0,0) and [3,3) both denote the empty interval. Note that [3,0) is not a valid interval, because an interval [x,y) must have x <= y.
• An interval I₁ is called a PROPER SUBSET of an interval I₂ if I₂ contains all elements of I₁ and at least one other element.
• A CHAIN is a nonempty sequence of intervals such that each interval (except for the last one) is a proper subset of the next interval.
• A CHAIN OF ORDER n is any chain such that the last interval in the chain is either the interval [0,n) or its proper subset.
• The LENGTH OF A CHAIN is the number of intervals that form it. (I.e., a chain is a sequence of objects, and when we talk about its length, we mean the length of that sequence.)
• A MAXIMAL CHAIN OF ORDER n is any chain such that no other chain of order n has a greater length.
• Given a chain { I₀, I₁, ..., I_m }, its CHARACTERISTIC SEQUENCE is any sequence of integers c₀, ..., c_m-1 such that for all i, c_i belongs into I_i+1 but not into I_i.

You are given a nonempty int[] c. Do the following:

• If c is a valid characteristic sequence of some maximal chain of order C, return "maximal C". Note that the correct C is always unique.
• If c is a valid characteristic sequence of some chain but not of any maximal chain, return "valid B". Here, B should be the smallest integer such that after examining the first B elements of c we can be certain that it isn't the characteristic sequence of any maximal chain.
• If c is not a valid characteristic sequence of any chain, return "invalid A", where A is the smallest integer such that after examining the first A elements of c we can be certain that it's not a valid characteristic sequence at all.