시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 1024 MB160918364.844%

문제

길이가 $N$인 수열 $A$가 주어진다. 수열의 $i$번째 원소($A_i$)로 끝나는 증가하는 부분 수열의 개수를 출력하는 프로그램을 작성하자.

단, 수가 너무 커질 수 있으니 $998\,244\,353$으로 나눈 나머지를 출력한다.

 

증가하는 부분 수열이 무엇인지 잘 모르는 친구들은 친절한 동원이가 준비한 아래 정의를 읽어보도록 하자.

  • 부분 수열이란 주어진 수열에서 1개 이상의 원소를 골라 원래 순서대로 나열하여 얻은 수열을 말한다.
  • 증가하는 부분 수열이란 맨 처음 원소를 제외한 모든 원소가 바로 전 원소보다 큰 수열을 말한다. 다시 말해 길이가 $N$인 부분 수열 $A$가 있을 때, $A_{i-1} < A_i$ ($2 \le i \le N$) 를 만족하면 $A$는 증가하는 부분 수열이다.

동원이는 위 정의에 따라 길이가 $1$인 부분 수열은 항상 증가하는 부분 수열임에 주의하면 좋겠다는 메모를 추신으로 남겼다.

입력

첫째 줄에 수열의 길이 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots , A_N$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 $N$개의 정수를 출력한다.

$i$번째로 출력하는 수는 $A_i$로 끝나는 증가하는 부분 수열의 개수를 $998\,244\,353$로 나눈 값이다.

제한

  • $1 \leq N \leq 5\,000$
  • $1 \leq A_i \leq 5\,000$

예제 입력 1

5
1 2 3 4 5

예제 출력 1

1 2 4 8 16

예제 입력 2

5
1 1 1 1 1

예제 출력 2

1 1 1 1 1

예제 입력 3

5
1 2 2 4 3

예제 출력 3

1 2 2 6 6

출처

High School > 선린인터넷고등학교 > 제5회 천하제일 코딩대회 본선 I번