# PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

# DIFFICULTY:

EASY-MEDIUM

# DRAFT EXPLANATION:

**Note:** The editorial is underway. To not keep you waiting however, the draft editorial of the author is attached below.

A given final configuration i_1<i_2<...<i_k of indexes of *remaining* slippers is possible if and only if s_{i_j} \ge s_i for some i_j<i implies that i=i_{j'} for some j < j'. Consider the indexes of running maximums m_1<m_2<...<m_h of (s_{i_j}). The crucial observation is that (m_j) identifies the sequence (i_j) and all the increasing subsequences are valid sequences of running maximums. Hence, the answer to the problem is the number of strictly increasing subsequences, which may be computed (with a Fenwick tree) in O(N\log(N)).