Vudu

Ο νεαρός Mirko αγοράζει κούκλες βουντού τον τελευταίο καιρό. Λαμβάνοντας υπόψη ότι ενδιαφέρεται πολύ για τη φθηνότερη δυνατή αγορά, παρακολουθεί καθημερινά τις τιμές των κούκλων βουντού. Ο τιμοκατάλογος του αποτελείται από τις τιμές κουκλών τις τελευταίες ~N~ ημέρες, όπου η τιμή κούκλας ~a_i~ αντιπροσωπεύει την τιμή μιας κούκλας πριν από ~i~ μέρες.

Ο Mirko πιστεύει ότι έχει παρατηρήσει μια σύνδεση μεταξύ της μέσης τιμής της κούκλας σε μια σειρά διαδοχικών ημερών και της τιμής της επόμενης ημέρας. Θέλει να δοκιμάσει την προαίσθησή του και προβληματίζεται με μια πολύ ενδιαφέρουσα ερώτηση: "Για ένα δεδομένο ~P~ , πόσες διαφορετικές διαδοχικές υποακολουθίες τις τελευταίες ~N~ ημέρες υπάρχουν, όταν η μέση τιμή της κούκλας ήταν μεγαλύτερη ή ίση με το ~P~;"

Δύο διαδοχικές υποακολουθίες θεωρούνται διαφορετικές εάν η αρχή ή το τέλος τους είναι διαφορετικές.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~N~, το μήκος της ακολουθίας ~(1 \leq N \leq 1\,000\,000)~.
Η δεύτερη γραμμή εισόδου περιέχει ~N~ τιμές ~a_i\;(0 \leq a_i \leq 1\,000\,000\,000)~.
Η τρίτη γραμμή εισόδου περιέχει έναν ακέραιο αριθμό ~P\;(0 \leq P \leq 1\,000\,000\,000)~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει την απάντηση στην ερώτηση του Mirko για ένα δεδομένο ~P~.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 30% των πόντων, το μήκος της ακολουθίας ~N~ θα είναι μικρότερο ή ίσο με ~10\,000~.

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

input

3
1 2 3
3

output

1

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

Η μόνη υποακολουθία που έχει μέσο όρο μεγαλύτερο ή ίσο με ~3~ είναι η ~\{3\}~.

input

3
1 3 2
2

output

5

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

Οι υποακολουθίες που έχουν μέσο όρο μεγαλύτερο ή ίσο με ~2~ είναι ~\{1,\;3\},\;\{1,\;3,\;2\},\;\{3\},\;\{3,\;2\},\;\{2\}~.

input

3
1 3 2
3

output

1