Fancy Fence
시간 제한1초메모리 제한32 MB
높이 h_i와 너비 w_i를 가진 N개의 구간으로 이루어진 히스토그램 위에 놓이는 정수 좌표 축 정렬 직사각형의 개수를 10^9+7로 나눈 나머지를 구한다.
문제
Balázs는 마을에서 가장 멋진 울타리를 가지고 있다. 이 울타리는 N개의 멋진 구역으로 이루어져 있다. 구역은 땅 위에 서로 붙어 있는 직사각형이다. i번째 구역의 높이는 정수 hi이고 너비는 정수 wi이다.
이 멋진 울타리 위에서 멋진 직사각형을 찾으려고 한다.
직사각형이 멋지려면 다음 조건을 만족해야 한다.
- 변이 가로 또는 세로이고 길이가 정수이다
- 직사각형과 땅 사이의 거리가 정수이다
- 직사각형과 첫 번째 구역의 왼쪽 변 사이의 거리가 정수이다
- 직사각형이 완전히 구역 위에 놓여 있다
멋진 직사각형의 개수는 몇 개인가?
개수가 매우 클 수 있으므로 109 + 7로 나눈 나머지를 구한다.
입력
첫째 줄에는 구역의 수 N이 주어진다.
둘째 줄에는 공백으로 구분된 N개의 정수가 주어지며, i번째 수는 hi이다.
셋째 줄에는 공백으로 구분된 N개의 정수가 주어지며, i번째 수는 wi이다.
출력
멋진 직사각형의 개수를 109 + 7로 나눈 나머지를 한 줄에 출력한다. 따라서 출력 범위는 0, 1, 2, . . . , 109 + 6이다.
제한
- 1 ≤ N ≤ 105
- 1 ≤ hi, wi ≤ 109
힌트
모양이 
인 멋진 직사각형은 5개이다.
모양이 
인 멋진 직사각형은 3개이다.
모양이 
인 멋진 직사각형은 1개이다.
모양이 
인 멋진 직사각형은 2개이다.
모양이 
인 멋진 직사각형은 1개이다.