Counting Independent Dominating Sets in an Inversion Graph

Given a permutation ( p_1, p_2, \dots, p_n ) of ( [1,n] ), an inversion pair is a pair ( (i,j) ) with ( i<j ) and ( p_i > p_j ). The inversion graph is an undirected graph on ( n ) vertices where an edge exists between vertices ( i ) and ( j ) if and only if ( (i,j) ) is an inversion pair (note that edges are considered without orientation).

An independent set in a graph is a set of vertices in which no two vertices are adjacent. A dominating set is a set of vertices such that every vertex not in the set has at least one neighbor in the set. An independent dominating set (i.e. a maximal independent set) is a vertex set that is both independent and dominating.

Your task is: given the inversion graph of the permutation, count the number of independent dominating sets in the graph. It is guaranteed that the answer does not exceed ( 10^{18} ).

inputFormat

The first line contains an integer ( n ), the length of the permutation. The second line contains ( n ) space‐separated integers representing the permutation ( p ). It is guaranteed that ( p ) is a permutation of ( [1,n] ).

outputFormat

Output a single integer: the number of independent dominating sets in the inversion graph of the given permutation.

sample

2
1 2

1