Lettere d'amore

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: newlines.c
• Scarica la traccia in C++: newlines.cpp
• Scarica la traccia in Python: newlines.py
• Scarica la traccia in Java: newlines.java
• Scarica la traccia in C#: newlines.cs
• Scarica la traccia in JavaScript: newlines.html
• Scarica la traccia in Rust: newlines.rs

Descrizione del problema

Filippo sta scrivendo una nuova lettera d'amore per la sua ragazza. Per far colpo, Filippo ha scelto di utilizzare un font (il tipo di carattere) che fosse accattivante e la sua scelta è ricaduta su un font monospace, ovvero un font in cui tutti i caratteri hanno la stessa larghezza. Infatti questo font è stato un grande successo nell'ultima lettera che aveva scritto per la sua ragazza!

La sua ultima lettera era composta da $N$ parole lunghe $W_0$, $W_1$, $\ldots$, $W_{N-1}$ separate da uno spazio. Dato che il contenuto della lettera non stava tutto in una sola riga, Filippo aveva suddiviso il testo in righe aggiungendo dei caratteri "a capo" rappresentati come parole speciali con $W_i=-1$.

Filippo ha scritto la sua ultima lettera mandando il testo a capo esattamente dopo $K$ caratteri: più precisamente, non esiste una riga più lunga di $K$ caratteri e ogni riga va a capo soltanto quando non è possibile aggiungere un'altra parola alla riga senza superare $K$ caratteri.

Filippo è molto pignolo e vuole che la larghezza della sua prossima lettera sia uguale a quella della scorsa lettera, ovvero che anche nella prossima lettera il testo vada a capo esattamente dopo $K$ caratteri. Tuttavia Filippo si è dimenticato qual è il valore di $K$ che aveva usato nella prima lettera!

Aiutalo a trovare il minimo e il massimo valore che $K$ potrebbe avere.

Esempi

Come primo esempio, considera la lettera:

Sei bella
come un grafo

In questo caso, l'unica lunghezza di riga compatibile con gli acapi è di $13$ caratteri.

Come secondo esempio, considera la lettera:

Lorem ipsum dolor sit amet consectetur
adipiscing elit sed do eiusmod tempor
incididunt ut labore et dolore magna aliqua

In questo caso, la larghezza minima di riga è $43$ caratteri, mentre la larghezza massima è $47$ caratteri.

Assunzioni

• $T = 25$, saranno presenti esattamente $25$ casi di test.
• $3 \le N \le 50\,000$.
• $1 \le W_i \le 10^9$ oppure $W_i = -1$ per $i = 0, \ldots, N-1$.
• Ogni caso di test contiene almeno un valore $W_i = -1$.
• $W_0 \neq -1$ e $W_{N-1} \neq -1$
• $W$ non contiene due valori $-1$ consecutivi.
• È garantito che ogni riga è lunga al massimo $10^9$ caratteri.
• È garantito che esiste sempre almeno un valore $K$ valido e il numero di valori $K$ validi è finito.

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 da due righe. La prima riga contiene $N$, il numero totale di parole e caratteri di "a capo" presenti nella lettera. La seconda riga contiene $N$ interi $W_0, \ldots, W_{N-1}$, la lunghezza di ciascuna parola, oppure $-1$ per rappresentare un carattere "a capo".

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, il file di output deve contenere una riga con la dicitura:

Case #t: K1 K2

dove t è il numero del caso di test (a partire da $1$) e (K1, K2) rappresentano il valore minimo e massimo che può assumere $K$ nella prima lettera di Filippo.

Esempi di input/output

Gli esempi descritti sopra si rappresentano nel formato di input/output nel seguente modo.

---

Input:

2

6
3 5 -1 4 2 5

21
5 5 5 3 4 11 -1 10 4 3 2 7 6 -1 10 2 6 2 6 5 6

---

Output:

Case #1: 13 13
Case #2: 43 47

---