Zatopljenje

Είναι χειμώνας, δεν έχει κάνει ποτέ περισσότερο κρύο, και ο κ. Malnar κοιτάζει τις φωτογραφίες του από την τελευταία του κρουαζιέρα στην Αδριατική και αναπολεί αξέχαστες στιγμές. Στο βάθος είναι ανοιχτή η τηλεόραση και μεταδίδει ειδήσεις σχετικά με τις τελευταίες προτάσεις μέτρων για την επιβράδυνση της ανόδου της στάθμης της θάλασσας. Κοιτάζοντας τις φωτογραφίες του από την ακτή, ο κ. Malnar αναρωτιέται πώς θα ήταν οι φωτογραφίες αν η στάθμη της θάλασσας είχε ανέβει κατά ένα ορισμένο ποσό. Υπάρχουν τόσες πολλές φωτογραφίες και ακόμη περισσότερες ερωτήσεις, γι' αυτό ο κ. Malnar ζητά τη βοήθειά σας.

Φανταζόμαστε την ακτή ως μια ακολουθία n αριθμών ~h_{1}~, ~h_{2}~, ~...~ , ~h_{n}~, όπου ο ~i~-οστός αριθμός αντιπροσωπεύει το ύψος του ανάγλυφου στο i-οστό σημείο. Ο κ. Malnar έχει ~q~ ερωτήματα, όπου το ~i~-οστό ερώτημα έχει ως εξής: Πόσα νησιά θα υπήρχαν μεταξύ του ~l_{i}~-οστού και του ~r_{i}~-οστού σημείου εάν η στάθμη της θάλασσας είχε ανέβει κατά ~x_{i}~ μέτρα;?

Η αριστερή εικόνα δείχνει το πρώτο ερώτημα του πρώτου παραδείγματος, και η δεξιά εικόνα δείχνει το δεύτερο ερώτημα του δεύτερου παραδείγματος.
Οι αριστερές νησίδες αντιστοιχούν στα διαστήματα ~[2,\;2]~ και ~[4,\;5]~.
Οι δεξιές νησίδες αντιστοιχούν στα διαστήματα ~[1,\;1]~, ~[4,\;4]~, ~[8,\;8]~ και ~[10,\;10]~.

Ένα νησί ορίζεται ως το μέγιστο διάστημα όπου κάθε ~h_{i}~ είναι αυστηρά μεγαλύτερο από το επίπεδο της θάλασσας. Ένα μέγιστο διάστημα είναι αυτό που δεν μπορεί να επεκταθεί προς οποιαδήποτε κατεύθυνση διατηρώντας την προαναφερθείσα συνθήκη αληθή. Αρχικά, η στάθμη της θάλασσας είναι στα ~0~ μέτρα.

Είσοδος

Η πρώτη γραμμή θα περιέχει τους ακέραιους αριθμούς ~n~ και ~q\;(1 \le n,q \le 2 * 10^{5})~, το μήκος της ακολουθίας και τον αριθμό των ερωτήσεων.

Η δεύτερη γραμμή θα περιέχει ~n~ ακέραιους ~h_{1}~, ~h_{2}~, ~. . .~ , ~h_{n}~ ~(0 \le h_{i} \le 10^{9})~ που θα περιγράφουν το ανάγλυφο της ακτής.

Σε κάθε μία από τις επόμενες ~q~ γραμμές θα υπάρχουν τρεις ακέραιοι αριθμοί ~l_{i}~, ~r_{i}~ και ~x_{i}\;(1 \le l_{i} \le r_{i} \le n,\;0 \le x_{i} \le 10^9)~ που θα περιγράφουν το ~i~-οστό ερώτημα.

Έξοδος

Στην ~i~-οστή από τις ~q~ γραμμές εκτυπώστε την απάντηση στο ~i~-οστό ερώτημα. Κάθε ένα από τα ερωτήματα είναι ανεξάρτητο από το άλλα.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~10~	~n,q \le 2*10^{3}~
~2~	~20~	~l_{i} = 1,\;r_{i} = n~ για κάθε ~i = 1,\;2,\;...,\;q~
~3~	~20~	Υπάρχει ένας ακέραιος ~p\;(1 \le p \le n)~ τέτοιος ώστε να ισχύει το εξής: ~h_{1} \ge h_{2} \ge ... \ge h_{p}\;i\;h_{p} \le h_{p+1} \le ... \le h_{n}~
~4~	~60~	Κανένας επιπλέον περιορισμός

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

input

6 3
2 4 2 3 4 1
2 5 2
3 5 3
3 4 4

output

2
1
0

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

Το πρώτο ερώτημα παρουσιάζεται στην αριστερή εικόνα στην περιγραφή της άσκησης, οι νησίδες αντιστοιχούν στα διαστήματα ~[2,\;2]~ και ~[4,\;5]~. Στο δεύτερο ερώτημα η νησίδα αντιστοιχεί στο διάστημα ~[5,\;5]~. Στο τρίτο ερώτημα δεν υπάρχουν νησίδες επειδή τα πάντα είναι κάτω από το νερό.

input

10 3
5 0 3 4 2 0 1 6 3 5
3 9 1
1 10 3
1 10 2

output

2
4
3

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

Στο πρώτο ερώτημα οι νησίδες αντιστοιχούν στα διαστήματα ~[3,\;5]~ και ~[8,\;9]~. Στο δεύτερο ερώτημα (που φαίνεται στη δεξιά εικόνα στην περιγραφή της άσκησης) οι νησίδες αντιστοιχούν στα διαστήματα ~[1,\;1]~, ~[4,\;4]~, ~[8,\;8]~ και ~[10,\;10]~, ενώ στο τρίτο ερώτημα οι νησίδες αντιστοιχούν στα διαστήματα ~[1,\;1]~, ~[3,\;4]~ και ~[8,\;10]~.