Codeforces J. Monotonic Renumeration(그룹)

제목 설명:
You are given an array consisting of nmonotonic renumeration as an array b consisting of\(n\)integers such that all of the following conditions are met:

b1=0;

for every pair of indices iand jsuch that 1≤i,j≤n, then\(b_i=b_j\), it is still possible that\(b_i=b_j\) for every index i∈[1,n−1] either\(b_i=b_{i+1}\) or\(b_{i+1}\)=\(b_i\)+1

For example, if a=[1,2,1,2,3], then two possible monotonic renumerations of are b=[0,0,0,0,0]\(b=[0,0,0,0,1]\).
Your task is to calculate the number of different monotonic renumerations of a. The answer may be large, so print it modulo\(998244353\).
Input
The first line contains one integer n(\(2\leq{n}\leq{2*10^5}\)) — the number of elements in a
The second line contains n
integers (\(1≤a_i≤10^9\))
Output
Print one integer — the number of different monotonic renumerations of a, taken modulo 998244353.
Examples
Input
Copy

5
1 2 1 2 3

Output
Copy

2

Input
Copy

2
100 1

Output
Copy

2

Input
Copy

4
1 3 3 7

Output
Copy

4

아이디어:
제목의 뜻은 수열 a를 주고 수열 b를 구성하는 것이다. 다음과 같은 규칙에 따라 a에 같은 원소가 있다면 같은 원소의 위치가 b에 대응하는 원소도 반드시 동일해야 한다.그리고 b 시비 감수열, 한 번에 최대 1 증가
그러면 우리는 a와 같은 원소의 위치가 b의 위치에 대응하고 이 위치 사이의 모든 원소는 b에서 반드시 같아야 한다는 것을 알 수 있다.왜냐하면 b의 원소는 이전과 같거나 크거나 하기 때문이다.
제목은 중합된 구간을 찾아서 합치면 전체 중합 구간을 얻을 수 있고 이 전체 구간의 요소는 b에서 반드시 같아야 한다.
입력할 때 모든 원소의 가장 먼 동일한 원소의 위치를 기록할 수 있으며, 같은 원소가 없으면 그 자체의 위치를 기록할 수 있다.그리고 그룹을 한 번 훑어보고 현재 겹치는 구간의 오른쪽 단점을 기록합니다.만약 원소의 위치가 현재 중합구간 오른쪽 단점 안에 있다면 원소는 반드시 같아야 하며 선택할 수 없으면 중합구간 오른쪽 단점을 계속 업데이트한다.원소의 위치가 구간의 오른쪽 단점보다 크다는 것은 중합구간에 있지 않다는 것을 의미한다. 원소의 크기를 선택할 수 있다. 두 가지 선택법이 있는데 전체 결과는 2를 곱한 다음에 구간의 오른쪽 단점을 현재 위치로 업데이트하고 계속 반복한다.이 구간 안에 있지 않은 것 자체가 새로운 중합 구간일 수 있으니 주의하십시오. 중합 구간 안에 있지 않은 점만이 아닙니다.알고리즘에 2를 곱하여 오른쪽 단점을 업데이트하면 정확하게 계속 실행할 수 있다.
코드:

#include 
#include 

전재 대상:https://www.cnblogs.com/zhanhonhao/p/11287854.html