题目描述

quailty和tangjz正在玩一个关于线段的游戏。在平面上有n条线段，编号依次为1到n。其中第i条线段的两端点坐 标分别为(0,i)和(1,p_i)，其中p_1,p_2,...,p_n构成了1到n的一个排列。quailty先手，他可以选择一些互不相交 的线段，将它们拿走，当然他也可以一条线段也不选。然后tangjz必须拿走所有剩下的线段，若有两条线段相交， 那么他就输了，否则他就赢了。注意若quailty拿走了全部线段，那么tangjz也会胜利。quailty深深喜欢着tangjz ，所以他不希望tangjz输掉游戏，请计算他有多少种选择线段的方式，使得tangjz可以赢得游戏。

输入格式

第一行包含一个正整数n(1<=n<=100000)，表示线段的个数。 第二行包含n个正整数p_1,p_2,...,p_n(1<=p_i<=n)，含义如题面所述。

输出格式

输出一行一个整数，即tangjz胜利的方案数，因为答案很大，请对998244353取模输出。

5
1 2 4 5 3

8

提示

没有写明提示

题目来源

鸣谢Claris上传试题