Rezolvare PBinfo #959

Fie \( X = \overline{X_1 X_2 X_3…X_N} \) un număr natural din N cifre.

Definim secvență în numărul X orice număr format dintr-un grup de cifre situate pe poziții consecutive în X. De exemplu, pentru X=12543644 pot fi secvențe numerele: 5436, 12, 1, 364, 12543644, etc.

Definim secvență-maxim în șirul \(X\) o secvență \( \overline{X_K X_{K+1}…X_P…X_T} \) în care există o singură cifră \( X_P \) astfel încât \( X_K < X_{K+1} <…< X_P > X_{P+1} >…> X_T \) ( \(1≤K<P<T≤N\) și \(K,P,T\) sunt numere naturale). De exemplu, pentru X=12543644 secvențele-maxim sunt: 1254, 12543, 254, 2543, 364.

Cerință

Scrieți un program care citește numărul N, cele N cifre ale numărului X și care determină numărul total de secvenţe-maxim din numărul X.

Date de intrare

Fișierul de intrare secmax.in conține pe prima linie numărul natural N. Pe următoarea linie se află o succesiune de N cifre X1X2...XN, reprezentând cifrele numărului X.

Date de ieșire

Fișierul de ieșire secmax.out va conține pe prima linie un număr natural, reprezentând numărul total de secvenţe-maxim din numărul X.

Restricții și precizări

• 8 ≤ N ≤ 25000
• 0 ≤ X1, X2 , ..., XN ≤ 9
• X1 ≠ 0
• o secvență-maxim este formată din cel puțin trei cifre

Exemplu:

secmax.in

8
12543644

secmax.out

5

Explicație

Cifrele numărului X sunt: 1, 2, 5, 4, 3, 6, 4, 4.
Numărul conține 5 secvențe-maxim. Acestea sunt: 1254, 12543, 254, 2543, 364.