Майк и !Майк соперничают еще со школьных лет, они противоположны во всем что делают, кроме программирования. Сегодня у них возникла проблема, которую сами друзья сами решить не могут, но вместе с вами — кто знает?
Каждый из них знает две последовательности n чисел a и b. По запросу в виде пары целых чисел (l, r) Майк может сразу сообщить значение 
, а !Майк — значение 
.
Предположим, что робот задает им каждый из возможных различных запросов в виде пары целых чисел (l, r) (1 ≤ l ≤ r ≤ n) (то есть он сделает ровно n(n + 1) / 2 запросов) и считает, сколько раз их ответы на один и тот же запрос совпадают, то есть для скольких пар выполняется 
.
Сколько случаев совпадения посчитает робот?
Выходные данные
Выведите одно целое число — количество совпадений ответов, которые посчитает робот, то есть для скольких пар выполняется .
Примечание
В первом примере входных данных всего два совпадения:
1.l = 4,r = 4 since max{2} = min{2}.
2.l = 4,r = 5 since max{2, 1} = min{2, 3}.
Во втором примере входных данных совпадений не произойдет, так как ответ Майка на любой запрос всегда 3, в то время как !Майк всегда будет отвечать 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2 3 2 1 4
6 7 1 2 3 2
|
2
|
|
2
|
3
3 3 3
1 1 1
|
0
|