문제
길이가 $N$인 두 수열 $A_1, \cdots, A_N; B_1, \cdots, B_N$이 주어집니다. 아래 조건을 모두 만족시키는 $(i, j)$ 정수쌍의 개수를 구하세요. $\min$과 $\max$는 각각 최솟값과 최댓값을 의미합니다.
- 1ドル \le i \le j \le N$
- $\min(A_i, A_{i+1}, \cdots, A_j) = \min(B_i, B_{i+1}, \cdots, B_j)$
- $\max(A_i, A_{i+1}, \cdots, A_j) = \max(B_i, B_{i+1}, \cdots, B_j)$
출력
문제의 조건을 만족시키는 $(i, j)$ 정수쌍의 개수를 출력하세요.
두 정수쌍은 다음과 같습니다.
- $(i, j) = (2, 3)$이고, 구간의 최솟값은 1ドル,ドル 최댓값은 2ドル$로 같습니다.
- $(i, j) = (1, 4)$이고, 구간의 최솟값은 1ドル,ドル 최댓값은 3ドル$으로 같습니다.
W3sicHJvYmxlbV9pZCI6IjI4NDM0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiU2FtZSBSYW5nZSIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZTM4XHVjNzc0XHVhYzAwICROJFx1Yzc3OCBcdWI0NTAgXHVjMjE4XHVjNWY0ICRBXzEsIFxcY2RvdHMsIEFfTjsgQl8xLCBcXGNkb3RzLCBCX04kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViOWNjXHVjODcxXHVjMmRjXHVkMGE0XHViMjk0ICQoaSwgaikkIFx1YzgxNVx1YzIxOFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjMTM4XHVjNjk0LiAkXFxtaW4kXHVhY2ZjICRcXG1heCRcdWIyOTQgXHVhYzAxXHVhYzAxIFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1YWNmYyBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiQxIFxcbGUgaSBcXGxlIGogXFxsZSBOJDxcL2xpPlxyXG5cdDxsaT4kXFxtaW4oQV9pLCBBX3tpKzF9LCBcXGNkb3RzLCBBX2opID0gXFxtaW4oQl9pLCBCX3tpKzF9LCBcXGNkb3RzLCBCX2opJDxcL2xpPlxyXG5cdDxsaT4kXFxtYXgoQV9pLCBBX3tpKzF9LCBcXGNkb3RzLCBBX2opID0gXFxtYXgoQl9pLCBCX3tpKzF9LCBcXGNkb3RzLCBCX2opJDxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQgJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgxIFxcbGUgTiBcXGxlIDI1MFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgJE4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkQV8xLCBcXGNkb3RzLCBBX04kIFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgxIFxcbGUgQV9pIFxcbGUgMTBeOSkkPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDAgJE4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkQl8xLCBcXGNkb3RzLCBCX04kIFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgxIFxcbGUgQl9pIFxcbGUgMTBeOSkkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWMyZGNcdWQwYTRcdWIyOTQgJChpLCBqKSQgXHVjODE1XHVjMjE4XHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlx1YjQ1MCBcdWM4MTVcdWMyMThcdWMzMGRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kKGksIGopID0gKDIsIDMpJFx1Yzc3NFx1YWNlMCwgXHVhZDZjXHVhYzA0XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0MCAkMSQsIFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0MCAkMiRcdWI4NWMgXHVhYzE5XHVjMmI1XHViMmM4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kKGksIGopID0gKDEsIDQpJFx1Yzc3NFx1YWNlMCwgXHVhZDZjXHVhYzA0XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0MCAkMSQsIFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0MCAkMyRcdWM3M2NcdWI4NWMgXHVhYzE5XHVjMmI1XHViMmM4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjg0MzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTYW1lIFJhbmdlIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIHR3byBpbnRlZ2VyIHNlcXVlbmNlcyAkQV8xLCBcXGNkb3RzLCBBX04kIGFuZCAkQl8xLCBcXGNkb3RzLCBCX04kIG9mIGxlbmd0aCAkTiQuIEZpbmQgdGhlIG51bWJlciBvZiBwYWlycyBvZiBpbnRlZ2VycyAkKGksIGopJCB3aGljaCBzYXRpc2Z5IGFsbCBvZiB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnMuICRcXG1pbiQgYW5kICRcXG1heCQgZnVuY3Rpb25zIGRlbm90ZSB0aGUgbWluaW11bSBhbmQgbWF4aW11bSB2YWx1ZXMsIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kMSBcXGxlIGkgXFxsZSBqIFxcbGUgTiQ8XC9saT5cclxuXHQ8bGk+JFxcbWluKEFfaSwgQV97aSsxfSwgXFxjZG90cywgQV9qKSA9IFxcbWluKEJfaSwgQl97aSsxfSwgXFxjZG90cywgQl9qKSQ8XC9saT5cclxuXHQ8bGk+JFxcbWF4KEFfaSwgQV97aSsxfSwgXFxjZG90cywgQV9qKSA9IFxcbWF4KEJfaSwgQl97aSsxfSwgXFxjZG90cywgQl9qKSQ8XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGxlbmd0aCBvZiB0aGUgc2VxdWVuY2UsICROJC4gJCgxIFxcbGUgTiBcXGxlIDI1MFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyAkTiQgaW50ZWdlcnMgJEFfMSwgXFxjZG90cywgQV9OJCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gJCgxIFxcbGUgQV9pIFxcbGUgMTBeOSkkPFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zICROJCBpbnRlZ2VycyAkQl8xLCBcXGNkb3RzLCBCX04kIHNlcGFyYXRlZCBieSBhIHNwYWNlLiAkKDEgXFxsZSBCX2kgXFxsZSAxMF45KSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgbnVtYmVyIG9mIHBhaXJzIG9mIGludGVnZXJzICQoaSwgaikkIHdoaWNoIHNhdGlzZnkgdGhlIGNvbmRpdGlvbnMgb2YgdGhlIHByb2JsZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5UaGUgdHdvIHBhaXJzIG9mIGludGVnZXJzIGFyZSBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiQoaSwgaikgPSAoMiwgMykkLCB3aGVyZSBib3RoIHRoZSBtaW5pbXVtIGFuZCBtYXhpbXVtIHZhbHVlcyBvZiB0aGUgcmFuZ2UgYXJlIHRoZSBzYW1lIGFzICQxJCBhbmQgJDIkLCByZXNwZWN0aXZlbHkuPFwvbGk+XHJcblx0PGxpPiQoaSwgaikgPSAoMSwgNCkkLCB3aGVyZSBib3RoIHRoZSBtaW5pbXVtIGFuZCBtYXhpbXVtIHZhbHVlcyBvZiB0aGUgcmFuZ2UgYXJlIHRoZSBzYW1lIGFzICQxJCBhbmQgJDMkLCByZXNwZWN0aXZlbHkuPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=