on ordered $(<_{1},<_{2})$-structures, then so is order-invariance.

We take a slightly more comprehensive approach and study the finite satisfiability problem for ${\ensuremath{\mathrm{ESO}^2}\xspace}$ on structures that are equipped with linear orders and successor relations; henceforth called *ordered structures*.

Some prior work on decidability of ${\ensuremath{\mathrm{ESO}^2}\xspace}$ and its monadic fragment ${\ensuremath{\mathrm{EMSO}^2}\xspace}$ (where only quantification of unary relations is allowed) on ordered structures has been done under the guise of the finite satisfiability problem for ${\ensuremath{\mathrm{FO}^2}\xspace}$. An almost complete characterization of the classes of finite ordered structures for which ${\ensuremath{\mathrm{EMSO}^2}\xspace}$ is decidable was obtained in a sequence of articles [@Manuel10; @SchwentickZ10; @Kieronski11; @SchwentickZ12; @ManuelZ13]. Only the case of finite ordered structures with at least three successor relations remains open. For ${\ensuremath{\mathrm{ESO}^2}\xspace}$ it is only known that it is decidable on the class of finite ordered $(<,{\ensuremath{{S}}})$-structures [@GradelR99; @Otto01; @CharatonikW15] and ${{\ensuremath{\mbox{\sc NExpTime}}\xspace}}$-complete for $({\ensuremath{{S}}}_1, {\ensuremath{{S}}}_2)$-structures [@CharatonikW13]. We note that the latter result combined with the observation from above establishes the decidability of successor-invariance. Here and in general, if both a symbol $<$ (or $<_i$) and ${\ensuremath{{S}}}$ (or ${\ensuremath{{S}}}_i$) occur in the signature of a structure, we assume that ${\ensuremath{{S}}}$ (or ${\ensuremath{{S}}}_i$) is interpreted by the induced successor of $<$ (or $<_i$).

Our main 