Salto del fieno

Attenzione: Questo task ha un tempo limite di 10 minuti per l'invio della soluzione. Una volta richiesto un input, il timer partirà in automatico, e dopo la scadenza non sarà più possibile inviare una soluzione per quell'input. È sempre possibile richiedere un nuovo input, per cui non preoccuparti se il timer scade: dovrai semplicemente richiedere e scaricare un nuovo input.

Per aiutarti con questo task, abbiamo preparato delle tracce di soluzione, che includono solo le parti di lettura dell'input e scrittura dell'output (da tastiera e su schermo). Puoi decidere se leggere/scrivere su file decommentando le opportune righe di codice.

• Scarica la traccia in C: fieno.c
• Scarica la traccia in C++: fieno.cpp
• Scarica la traccia in C#: fieno.cs
• Scarica la traccia in Go: fieno.go
• Scarica la traccia in JavaScript: fieno.html
• Scarica la traccia in Java: fieno.java
• Scarica la traccia in Pascal: fieno.pas
• Scarica la traccia in Python: fieno.py
• Scarica la traccia in VisualBasic: fieno.vb

Descrizione del problema

Dario sta organizzando una gara di salto delle balle di fieno. Il percorso di gara è composto da $N$ pile di balle fieno, l'$i$-esima pila è formata da $H_i$ balle di fieno. La gara parte dalla pila $i=0$ e va verso la pila $i=N-1$, dove $H_0 = H_{N-1} = 0$. Per vincere bisogna superare in ordine tutte le pile di fieno.

Ovviamente passare da pila ad un altra diventa più difficile se la pila è un picco prominente del percorso. Una pila è un picco se vale $H_{i-1} < H_i > H_{i+1}$ la prominenza di tale picco è il più grande intero $p$ tale che le pile $i-1$ e $i+1$ abbiano altezza minore o uguale di $H_i - p$. Le pile $0$ e $N-1$ non sono mai picchi. Dario vuole sapere quale è l'indice del picco con prominenza maggiore, sapresti aiutarlo? Attenzione a parità di prominenza Dario vuole sapere l'indice minore tra i picchi con prominenza massima. Se non esiste neanche un picco sul percorso la risposta dovrà essere $-1$.

Formato di input

La prima riga del file di input contiene un intero $T$, il numero di casi di test. Seguono $T$ casi di test, numerati da $1$ a $T$. Ogni caso di test è preceduto da una riga vuota.

Ogni caso di test è composto come segue:

• una riga contenente l'intero $N$.
• una riga contenente gli $N$ interi $H_{0}, \, \ldots, \, H_{N-1}$.

Formato di output

Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura:

Case #t: x

dove t è il numero del caso di test (a partire da $1$) e il valore x è l'indice del picco con prominenza massima.

Assunzioni

• $T = 10$, nei file di input che scaricherai saranno presenti esattamente $10$ casi di test.
• $2 \le N \le 100\,000$
• $0 \le H_i \le 1\,000\,000$ per ogni $i = 0, \, \dots, \, N-1$.

Nei primi $3$ casi di test solo una pila ha altezza diversa da $0$.

Esempi di input/output

Input:

3

4
0 4 2 0

4
0 3 0 0

7
0 1 3 1 4 2 0

Output:

Case #1: 1
Case #2: 1
Case #3: 2

Spiegazione

Nel primo caso d'esempio, l'unico picco è la pila di indice $1$ e ha prominenza $2$.

Nel terzo caso d'esempio, due pile sono picchi e hanno prominenza massima pari a $2$: la pila di indice $2$ e quella di indice $4$. Quindi il risultato sarà $2$ perchè è l'indice minore.