문제

2014 개정수학 수II의 함수 단원을 공부하던 수찬이는 반복적인 학습이 지겨워서, 문제집에서 다루지 않는 함수를 만들기로 했다!

수찬이는 자신의 이니셜을 딴 \texttt{sc}(A, x)$\texttt{sc}(A, x)$라는 함수를 만들기로 했다. A[1..n]$A[1..n]$는 길이가 n$n$인 자연수(1 이상의 정수)로 구성된 배열이고, x$x$는 자연수이다.

수찬이는 이 함수를 어떻게 정의하면 좋을지 고민하다가, 우연히 지학이를 만났다. 지학이는 배열에 아래와 같은 연산을 하며 놀고 있었다.

• 두 정수 l$l$과 r$r$ (1 \le l \le r \le n$1 \le l \le r \le n$)을 정한다.
• A[l], A[l+1], \cdots, A[r-1], A[r]$A[l], A[l+1], \cdots, A[r-1], A[r]$에 각각 1을 더한다.

수찬이는 이 모습을 보고, \texttt{sc}(A, x)$\texttt{sc}(A, x)$를 이렇게 정의하기로 했다.

• A[i] > x$A[i] > x$를 만족하는 i$i$ (1 \le i \le n$1 \le i \le n$)가 존재한다면 -1$-1$
• 존재하지 않는다면, A$A$의 모든 원소를 x$x$로 만들기 위해 지학이의 연산을 해야 하는 최소 횟수

수찬이는 함수를 정의한 기념으로, \texttt{sc}(A, k) = l$\texttt{sc}(A, k) = l$를 만족하는 길이가 n$n$인 서로 다른 배열 A$A$가 몇 개나 되는지 세고자 한다. 그러나 수찬이가 직접 세기에는 이러한 경우의 수가 너무나 많았다.

수찬이를 도와 경우의 수가 몇 개인지 세어 보자.