33996번 - 점진적인 수열

문제

수열 $A_1, A_2, \dots, A_N$이 점진적인 수열이라는 것은 수열의 길이가 3ドル$ 이상이고, 3ドル$ 이상 $N$ 이하인 모든 정수 $i$가 다음 세 가지 조건 중 하나를 만족한다는 뜻이다.

• $A_i-A_{i-1}$ $=$ $A_{i-1}-A_{i-2}-1$
• $A_i-A_{i-1}$ $=$ $A_{i-1}-A_{i-2}$
• $A_i-A_{i-1}$ $=$ $A_{i-1}-A_{i-2}+1$

서로 다른 정수로 이루어진 수열 $S_1, S_2, \dots, S_N$이 주어진다. 이 수열의 부분 수열이자 점진적인 수열의 길이 합을 구해보자.

입력

첫째 줄에 수열의 길이를 나타내는 정수 $N$이 주어진다. $(1\leq N \leq 3000)$

둘째 줄에 서로 다른 정수로 이루어진 수열 $S_1, S_2, \dots, S_N$이 공백으로 구분되어 주어진다. $(1 \leq S_i \leq 10^9)$

출력

첫째 줄에 수열 $S_1, S_2, \dots, S_N$의 부분 수열이자 점진적인 수열의 길이 합을 구해 출력한다. 단 정답이 너무 커질 수 있으니, 10ドル^9+7$로 나눈 나머지를 구해 출력한다.

제한

노트

어떤 수열의 부분 수열이라는 것은 그 수열에서 순서를 바꾸지 않고 몇 개의 원소를 제거해서 만들 수 있는 수열이다.