INF = 10 ** 10 N = gets.to_i A = gets.split.map(&:to_i) dp1 = [[INF, -INF]] dp2 = [[0, 1]] A.each do |a| m = dp1.bsearch_index do |dpm| dpm[-1] >= a end || dp1.size j = dp1[m - 1].bsearch_index{|a_| a_ <= a } b = dp2[m - 1][-1] - dp2[m - 1][j - 1] if m < dp1.size dp1[m] << a dp2[m] << dp2[m][-1] + b else dp1 << [INF, a] dp2 << [0, b] end end puts dp2[-1][-1]