Max

Θεωρήστε δύο φθίνουσες ακολουθίες ακεραίων ~X[0 \cdots n-1]~ και ~Y[0 \cdots n-1]~ με ~X[i] \ge X[i+1]~ και ~Y[i] \ge Y[i+1]~ και για όλα τα ~i~, ~0 \le i < n - 1~. Η απόσταση μεταξύ δύο στοιχείων ~X[i]~ και ~Y[j]~ δίνεται από τη σχέση:

~d(X[i],\,Y[j])\,=\,j - i~, εάν ~j \ge i~ και ~Y[j] \ge X[i]~, ή διαφορετικά ~0~.

Η απόσταση μεταξύ της ακολουθίας ~X~ και της ακολουθίας ~Y~ ορίζεται από τη σχέση:

~d(X,\,Y)\,=\,max\{d(X[i],\,Y[j])\,|\,0 \le i < n,\,0 \le j < n\}~

Μπορείτε να υποθέσετε ~0 < n < 1000~.

Για παράδειγμα, για τις παρακάτω ακολουθίες ~X~ και ~Y~, η μέγιστη απόστασή τους επιτυγχάνεται για ~i=2~ και ~j=7~, άρα ~d(X,\,Y)\,=\,d(X[2],\,Y[7])\,=\,5~.

         i=2
                  |
                  v
      X     8  8  4  4  4  3  3  3  1 

      Y     9  9  8  8  6  5  5  4  3
                                 ^
                                 |
                                j=7

Ερώτημα α Υπάρχει μια μέγιστη τιμή ~d(X,\,Y)~ σε όλες τις ακολουθίες ~X~ και ~Y~ μήκους ~n~. Ποια ιδιότητα πρέπει να ικανοποιούν οι ακολουθίες για να φτάσουν σε αυτήν την τιμή; Υπάρχει μια ελάχιστη τιμή ~d(X,\,Y)~. Ποια ιδιότητα πρέπει να ικανοποιούν οι ακολουθίες για να φτάσουν σε αυτήν την τιμή;

Ερώτημα β Γράψτε ένα πρόγραμμα που διαβάζει επανειλημμένα ένα ζεύγος ακολουθιών ακεραίων και εκτυπώνει την απόσταση μεταξύ αυτών των ακολουθιών. Η πρώτη ακολουθία είναι η ακολουθία ~X~ και η δεύτερη η ακολουθία ~Y~. Μπορείτε να υποθέσετε ότι οι ακολουθίες είναι φθίνουσες και ίσου μήκους. Ένα ζεύγος ακολουθιών προηγείται από έναν αριθμό σε μία μόνο γραμμή που δείχνει τον αριθμό των στοιχείων στις ακολουθίες. Οι αριθμοί σε μια ακολουθία χωρίζονται με ένα κενό και κάθε ακολουθία βρίσκεται σε μια γραμμή από μόνη της. Ως συνήθως, ο πρώτος αριθμός στην είσοδο δίνει τον αριθμό των περιπτώσεων δοκιμής. Προσπαθήστε να γράψετε ένα αποτελεσματικό πρόγραμμα.

Ερώτημα γ Δώστε μια πολύ σύντομη εξήγηση του προγράμματός σας. Επίσης, δώστε μια πρόχειρη εκτίμηση του μέγιστου αριθμού συγκρίσεων μεταξύ στοιχείων των δύο ακολουθιών που υπολογίζει το πρόγραμμά σας. (Για παράδειγμα, το ~n^2~ μπορεί να θεωρηθεί ως "εκτίμηση, κατά προσέγγιση" του ~n^2 - 4~.)

Παραδείγματα

input

2
9
8 8 4 4 4 3 3 3 1
9 9 8 8 6 5 5 4 3
7
6 5 4 4 4 4 4
3 3 3 3 3 3 3

output

The maximum distance is 5

The maximum distance is 0