Dizalo

Σε μια πόλη υπάρχει ένας ψηλός ουρανοξύστης με ~n~ ορόφους. Υπάρχουν ~n~ άνθρωποι που περιμένουν το ασανσέρ στο ισόγειο. Το ~i~-οστό άτομο θέλει να πάει στον όροφο ~a_{i}~. Δεν υπάρχει κανένα ζεύγος ατόμων που να θέλει να πάει στον ίδιο όροφο.

Ο ουρανοξύστης έχει ένα ασανσέρ που είναι αρκετά μεγάλο για να χωρέσουν όλοι οι άνθρωποι, αλλά είναι τόσο στενό που δεν μπορούν να σταθούν δίπλα-δίπλα- αλλά πρέπει να είναι όλοι ο ένας πίσω από τον άλλον.

Όλοι μπήκαν στο ασανσέρ, αλλά δεν είχαν σκεφτεί τη σειρά με την οποία πρέπει να βγουν από αυτό! Αρχικά, το ~i~-οστό άτομο βρίσκεται στη θέση ~i~, κοιτάζοντας από την πόρτα του ασανσέρ. Εάν ένα άτομο θέλει να βγει από το ασανσέρ, όλοι όσοι βρίσκονται μπροστά του (πιο κοντά στην πόρτα) πρέπει και αυτοί να βγουν προσωρινά από το ασανσέρ. Όταν επιστρέφουν πίσω στο ασανσέρ, μπορούν να επαναδιαταχθούν όπως επιθυμούν. Άτομα που βρίσκονται πίσω (πιο μακριά από την πόρτα) από το άτομο που θέλει να βγει δεν θα βγαίνουν από το ασανσέρ.

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

Ο Μίρκο βλέπει την κατάσταση στην οποία βρίσκονται και συλλογίζεται. Θέλει να μάθει πόσες έξοδοι από το ασανσέρ θα χρειάζονταν αν οι άνθρωποι που επιστρέφουν στον ανελκυστήρα επέστρεφαν πάντα με τον βέλτιστο τρόπο. Αν ένα άτομο βγαίνει από το ασανσέρ πολλές φορές, κάθε φορά μετριέται ως ξεχωριστή.

Ο Μίρκο είναι έμπειρος προγραμματιστής και μπορεί να λύσει αυτό το πρόβλημα αρκετά εύκολα. Η χαρά του όμως είναι σύντομη, γιατί δίπλα του είναι ο φίλος του ο Σλάβκο. Ο Σλάβκο σκέφτηκε ~q~ ερωτήσεις: Αν το άτομο στη θέση ~x_{i}~ δεν βρισκόταν στο ασανσέρ, πόσες έξοδοι θα γινόντουσαν τότε;

Ο Μίρκο ενδιαφέρεται για μια απάντηση πριν από την πρώτη ερώτηση του Σλάβκο και μετά από κάθε ερώτηση. Σημειώστε ότι για κάθε ερώτηση, όλα τα άτομα από τις προηγούμενες ερωτήσεις θεωρείται επίσης ότι δεν βρίσκονται στο ασανσέρ.

Ο Μίρκο άρχισε να λύνει το πρόβλημα, αλλά σύντομα συνειδητοποίησε ότι ακόμη και για τον ίδιο αυτό δεν θα ήταν αρκετά εύκολο. Βοηθήστε τον να λύσει αυτό το πρόβλημα!

Σημείωση: Το ασανσέρ θα κινείται πάντα από τον πρώτο όροφο στον ~n~-οστό όροφο και θα σταματά σε κάθε όροφο στον οποίο κάποιος θέλει να βγει.

Είσοδος

Η πρώτη γραμμή θα περιέχει δύο μη αρνητικούς ακέραιους αριθμούς ~n~ και ~q\;(0 \le q < n \le 10^{5})~, τον αριθμό των ατόμων/ορόφων και τον αριθμό των ερωτήσεων.

Η δεύτερη γραμμή θα περιέχει ~n~ ακέραιους αριθμούς ~a_{i}\;(1 \le a_{i} \le n,\;a_{i} \neq a_{j}~ για κάθε ~i \neq j)~, όπου ~a_{i}~ είναι ο όροφος στον οποίο το ~i~-οστό άτομο θέλει να βγει από το ασανσέρ. Η ακολουθία ~(a_{i})~ είναι μια μετάθεση.

Η τρίτη γραμμή θα περιέχει ~q~ ακέραιους αριθμούς ~x_{i}\;(1 \le x_{i} \le n,\;x_{i} \neq x_{j}~ για κάθε ~i \neq j)~, τις ερωτήσεις του Σλάβκο.

Έξοδος

Σε μία γραμμή, εκτυπώστε ~q + 1~ αριθμούς, όπου ο ~i~-οστός είναι ο αριθμός των εξόδων μετά από ~i - 1~ ερωτήσεις.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~16~	~n,q \le 100~
~2~	~19~	~n,q \le 1000~
~3~	~29~	~q = 0~
~4~	~46~	Κανένας επιπλέον περιορισμός

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

input

5 2
3 4 1 2 5
3 2

output

9 6 4

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

Η εικόνα δείχνει τις εξόδους από το ασανσέρ πριν από την πρώτη ερώτηση. Το ασανσέρ βρίσκεται στον πρώτο όροφο και το άτομο στη θέση ~3~ θέλει να να βγει. Όμως, για να μπορέσει να βγει, πρέπει πρώτα να βγουν τα άτομα στις θέσεις ~1~ και ~2~, και επιστρέφουν στο ασανσέρ στις ίδιες θέσεις.

Στη συνέχεια, στον δεύτερο όροφο, το άτομο στη θέση ~4~ θέλει να βγει. Και πάλι, τα άτομα στις θέσεις ~1~ και ~2~ πρέπει να βγουν πρώτα και επιστρέφουν στο ασανσέρ στις ίδιες θέσεις.

Μετά από αυτό, στον τρίτο όροφο, το άτομο στη θέση ~1~ βγαίνει από το ασανσέρ, χωρίς κανείς άλλος να χρειαστεί να βγει από το ασανσέρ.

Μετά από αυτό, στον τέταρτο όροφο, το άτομο στη θέση ~2~ βγαίνει από το ασανσέρ, χωρίς κανείς άλλος να χρειαστεί να βγει από το ασανσέρ.

Και τέλος, στον πέμπτο όροφο, το άτομο στη θέση ~5~ βγαίνει από το ασανσέρ.

Συνολικά, έγιναν ~3 + 3 + 1 + 1 + 1 = 9~ έξοδοι από το ασανσέρ.

input

7 0
4 5 2 1 6 3 7

output

13

input

3 2
3 1 2
1 2

output

5 2 1