Swap Swap Sort

Υπάρχει ένας πίνακας ~N~ ακεραίων, ο καθένας με τιμή μεταξύ ~1~ και ~K~. Ο φίλος σας έχει έναν αλγόριθμο που μπορεί να ταξινομήσει αυτόν τον πίνακα σύμφωνα με οποιαδήποτε σειρά των αριθμών από το ~1~ έως το ~K~. Ο αλγόριθμος εκτελεί μια ακολουθία πράξεων ανταλλαγής (swap), που ανταλλάσσουν δύο γειτονικά στοιχεία του πίνακα. Ο αλγόριθμος εκτελεί ακριβώς τον ελάχιστο αριθμό τέτοιων ανταλλαγών για να ταξινομήσει τον πίνακα.

Η επιθυμητή σειρά των αριθμών από το ~1~ έως το ~K~ δίνεται από μια μετάθεση στόχου. Μια μετάθεση στόχου είναι μια ακολουθία κάθε αριθμού από το ~1~ έως το ~K~ που εμφανίζεται ακριβώς μία φορά, στην ίδια σειρά με την αντίστοιχη επιθυμητή σειρά.

Για παράδειγμα, ο πίνακας [~1~ ~4~ ~2~ ~1~ ~2~] ταξινομημένος με βάση τη μετάθεση στόχου ~4~, ~1~, ~2~, ~3~ έχει ως αποτέλεσμα τον πίνακα [~4~ ~1~ ~1~ ~2~ ~2~].

Σας ενδιαφέρει ο αριθμός των ανταλλαγών που εκτελούνται από τον αλγόριθμο του φίλου σας για διαφορετικές μεταθέσεις στόχων. Για να το εξερευνήσετε αυτό, ξεκινάτε με μια μετάθεση στόχου ~1~, ~2~,..., ~K~ και εκτελείτε ~Q~ λειτουργίες σε αυτό. Κάθε πράξη ανταλλάσσει δύο γειτονικά στοιχεία της μετάθεσης στόχου. Μετά την εκτέλεση κάθε λειτουργίας, βρείτε τον αριθμό των ανταλλαγών που θα έκανε ο αλγόριθμος του φίλου σας εάν εκτελούνταν με την τρέχουσα μετάθεση στόχου. Οι ~Q~ λειτουργίες αλλάζουν σωρευτικά τη μετάθεση στόχου, αλλά δεν επηρεάζουν τον πίνακα.

Είσοδος

Η πρώτη γραμμή περιέχει τρεις ακέραιους αριθμούς ~K~ και ~Q~ ~(1 \le K \le N \le 100\,000,\,1 \le Q \le 1\,000\,000)~.

Η επόμενη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~a_1,\,a_2, \cdots, a_N~ ~(1 \le a_i \le K)~ που προσδιορίζουν τον πίνακα.

Οι επόμενες ~Q~ γραμμές περιέχουν η καθεμία ένα μοναδικό ακέραιο αριθμό ~j~ ~(1 \le j \le K - 1)~, που αντιπροσωπεύει την πράξη ανταλλαγής των στοιχείων της μετάθεσης στόχου στη θέση ~j~ και ~j+1~

Βαθμολογία

Για ~3~ από τους ~25~ διαθέσιμους βαθμούς, ~N~, ~Q \le 5\,000~.
Για επιπλέον ~3~ από τους ~25~ διαθέσιμους βαθμούς, ~Q \le 100~.
Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~K \le 500~.

Έξοδος

Για καθεμία από τις ~Q~ πράξεις, εκτυπώστε μια γραμμή που να περιέχει ένα μόνο ακέραιο αριθμό, την απάντηση για την τρέχουσα μετάθεση στόχου.

Παράδειγμα

input

5 4 3
1 4 2 1 2
3
2
1

output

4
2
2

Επεξήγηση του παραδείγματος

Οι τρεις μεταθέσεις στόχου είναι ~1~,~2~,~4~,~3~, έπειτα ~1~,~4~,~2~,~3~, έπειτα ~4~,~1~,~2~,~3~. Για την τελική μετάθεση στόχου, ο αλγόριθμος του φίλου σας χρησιμοποιεί δυο ανταλλαγές για να ταξινομήσει τον πίνακα από [~1~ ~4~ ~2~ ~1~ ~2~] σε [~4~ ~1~ ~1~ ~2~ ~2~].