Yana, Mino, White, Huzz는 단짝 친구입니다.

코치님의 고된 과제를 마침내 끝낸 Huzz는 휴식을 얻었습니다. 어느 나른한 오후, 세상은 다가오는 황혼의 따뜻하고 황금빛인 안개에 싸여 아주 느리게 흘러가는 듯했습니다. 산들바람은 커다란 참나무 잎사귀 사이로 비스듬히 쏟아지는 햇살 속에서 춤추는 먼지 입자들을 살짝 흔들 뿐이었습니다.

그 졸리고 편안한 공백 속에서, Huzz는 자신의 부드러운 상어 인형 안에서 순열 하나를 발견했습니다. 그는 재미 삼아 그것을 친구들과 공유하기로 했습니다.

Mino는 분할하기를 좋아합니다. 그는 이 순열을 여러 개의 연속된 구간으로 분할할 수 있습니다.

Yana는 교환하기를 좋아합니다. 그는 하나의 연속된 구간을 선택하여 그 구간의 최댓값 원소와 최솟값 원소를 서로 바꿀 수 있습니다.

구체적으로, 그들은 다음 두 가지 유형의 연산을 임의의 순서로 임의의 횟수만큼 수행할 수 있습니다:

• split: 길이가 $1$보다 큰 연속된 구간 하나를 선택합니다. 그런 다음 그 내부의 위치를 하나 골라 인접한 두 개의 연속된 구간으로 분할합니다. 예를 들어, $(a_i, \dots, a_j)$는 $(a_i, \dots, a_k)$와 $(a_{k+1}, \dots, a_j)$로 분할될 수 있습니다 ($i \le k < j$).
• swap: 연속된 구간 하나를 선택하고 그 최댓값 원소와 최솟값 원소를 교환합니다.

원하는 만큼 연산을 수행한 후 연산을 멈추고, 만들어진 모든 구간을 원래 순서대로 합쳐 새로운 순열을 만듭니다.

White는 세는 것을 좋아합니다. 그녀는 궁금해합니다 — 그들은 서로 다른 순열을 몇 개나 얻을 수 있을까요?

결과가 매우 클 수 있으므로, 답을 $998\,244\,353$으로 나눈 나머지만 구하면 됩니다.

입력

입력의 첫째 줄에는 순열의 길이를 나타내는 정수 $n$ ($1 \le n \le 500$)이 주어집니다.

둘째 줄에는 순열 자체를 나타내는 $n$개의 정수 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$)이 주어집니다. $\{a_n\}$이 순열임이 보장됩니다.

출력

그들이 얻을 수 있는 서로 다른 순열의 개수를 $998\,244\,353$으로 나눈 나머지를 나타내는 정수를 출력하세요.

예제

입력

4
1 4 2 3

출력

10

입력

7
5 1 4 2 6 3 7

출력

340

노트

첫 번째 예제에서 그들이 얻을 수 있는 모든 가능한 순열은 다음과 같습니다:

$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$