Майк и !Майк соперничают еще со школьных лет, они противоположны во всем что делают, кроме программирования. Сегодня у них возникла проблема, которую сами друзья сами решить не могут, но вместе с вами — кто знает?
Каждый из них знает две последовательности n чисел a и b. По запросу в виде пары целых чисел (l, r) Майк может сразу сообщить значение 
, а !Майк — значение 
.
Предположим, что робот задает им каждый из возможных различных запросов в виде пары целых чисел (l, r) (1 ≤ l ≤ r ≤ n) (то есть он сделает ровно n(n + 1) / 2 запросов) и считает, сколько раз их ответы на один и тот же запрос совпадают, то есть для скольких пар выполняется 
.
Сколько случаев совпадения посчитает робот?
В первой строке содержится единственное целое число n (1 ≤ n ≤ 200 000).
Во второй строке содержатся n целых чисел a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — элементы последовательности a.
В третьей строке содержатся n целых чисел b1, b2, ..., bn ( - 109 ≤ bi ≤ 109) — элементы последовательности b.
Выведите одно целое число — количество совпадений ответов, которые посчитает робот, то есть для скольких пар выполняется .
6
1 2 3 2 1 4
6 7 1 2 3 2
2
3
3 3 3
1 1 1
0
В первом примере входных данных всего два совпадения:
1.l = 4,r = 4 since max{2} = min{2}.
2.l = 4,r = 5 since max{2, 1} = min{2, 3}.
Во втором примере входных данных совпадений не произойдет, так как ответ Майка на любой запрос всегда 3, в то время как !Майк всегда будет отвечать 1.
| Codeforces Round 361 (Div. 2) |
|---|
| Закончено |
