시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB111453145.588%

문제

수열 $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$로 나눈 나머지를 구해 출력한다.

예제 입력 1

3
2 4 6

예제 출력 1

3

예제 입력 2

5
1 4 6 8 9

예제 출력 2

32

예제 입력 3

2
2 1

예제 출력 3

0

예제 입력 4

4
1 10 7 2

예제 출력 4

0

노트

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

출처

University > 서강대학교 > K512컵 > 2025 서강대학교 K512컵 H번