Squadre sbilanciate

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: basket.c
• Scarica la traccia in C++: basket.cpp
• Scarica la traccia in C#: basket.cs
• Scarica la traccia in Go: basket.go
• Scarica la traccia in JavaScript: basket.html
• Scarica la traccia in Java: basket.java
• Scarica la traccia in Pascal: basket.pas
• Scarica la traccia in Python: basket.py
• Scarica la traccia in VisualBasic: basket.vb

Descrizione del problema

Dario sta organizzando una partita a basket e ha già radunato due squadre di $N$ persone, che ha ordinato per altezza crescente e numerato da $0$ a $N-1$. L' $i$-esima persona della squadra A è alta $A_i$ metri, mentre l' $i$-esima persona della squadra $B$ è alta $B_i$ metri. Purtroppo si è accorto che le squadre così formate sono troppo sbilanciate. Per ovviare al problema, ha deciso di selezionare due squadre Alfa e Beta, composte rispettivamente da persone della squadra A e della squadra B, con lo stesso numero di giocatori. Inoltre, quando i giocatori di queste nuove squadre sono ordinati per altezza crescente, l' $i$-esima persona della squadra Alfa deve essere alta quanto l'$i$-esima della squadra Beta. Quante persone possono esserci, al massimo, nella squadra Alfa?

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 $A_{0}, \, \ldots, \, A_{N-1}$.
• una riga contenente gli $N$ interi $B_{0}, \, \ldots, \, B_{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 è il numero massimo di componenti nella squadra Alfa.

Assunzioni

• $T = 14$, nei file di input che scaricherai saranno presenti esattamente $14$ casi di test.
• $1 \le N \le 300000$
• $1 \le A_i, B_i \le 10^9$, per ogni $0 \le i < N$.
• $A_i \le A_{i+1}$ e $B_i \le B_{i+1}$, per ogni $1 \le i \le N$.

Nei primi $5$ casi di test vale $N\le 1000$ e $A_i, B_i \le 1000$, per ogni $0 \le i < N$.

Esempi di input/output

Input:

2

4
1 2 3 4
1 3 5 6

5
7 8 9 9 11
1 2 8 11 17

Output:

Case #1: 2
Case #2: 2

Spiegazione

Nel primo caso d'esempio è possibile selezionare come squadra Alfa le persone $0$ e $2$ della squadra A, di altezza rispettivamente $1$ e $3$ metri, e, come squadra Beta, i giocatori $0$ e $1$ della seconda squadra, di altezza rispettivamente $1$ e $3$ metri.

Nel secondo caso d'esempio è possibile selezionare come squadra Alfa le persone $1$ e $4$ della squadra A, di altezza rispettivamente $8$ e $11$ metri, e, come squadra Beta, i giocatori $2$ e $3$ della seconda squadra, di altezza rispettivamente $8$ e $11$ metri.