Algorithm (Monotone Stack)

1. Note that $A_{i:j}$ is a valid subarray if and only if $A_{i}\leq\max\{A_{i},…,A_{j}\}.$ So for each $j\in\{0,…,n-1\}$, where $n=|A|-1,$ the number of valid sequences ending in $A_{j}$ is equal to the cardinality of the set $$\mathcal{A}_{i}:=\{(i,j):A_{i}\leq A_{j}\text{ and }\max\{A_{i},…,A_{j}\}\geq A_{i}\}.$$
2. Notice that all $\mathcal{A}_{i}$’s could be obtained together in $O(N)$ complexity using monotone_stack data structure.

Code

template <class T, class Container = std::deque<T>>
struct size_view_creator {
  typedef std::size_t value_type;
  std::reference_wrapper<Container> data;
  std::size_t operator()() const { return data.get().size(); }
};

template <class T, class ViewCreator, class Comp = std::greater<>>
class monotone_stack {
 private:
  typedef T value_type;
  typedef typename ViewCreator::value_type view_value_type;

 private:
  std::deque<T> data_;
  std::vector<view_value_type> view_;
  ViewCreator view_creator_;
  Comp comp_;

 public:
  monotone_stack() : data_{}, view_{}, comp_{}, view_creator_{std::cref(data_)} {}

  template <typename InputIterator>
  monotone_stack(InputIterator first, InputIterator last) : data_{}, view_{}, comp_{}, view_creator_{std::ref(data_)} {
    for (auto it = first; it != last; ++it)
      this->emplace_back(*it);
  }

  std::size_t size() const { return std::size(data_); }
  std::vector<view_value_type>& view() const { return view_; }
  view_value_type view(std::size_t i) const { return view_[i]; }
  std::vector<value_type>& data() const { return data_; }

  void emplace_back(value_type elm) {
    while (not empty(data_) and comp_(data_.back(), elm))
      data_.pop_back();
    data_.emplace_back(elm);
    view_.emplace_back(view_creator_());
  }

  template <typename F>
  view_value_type reduce(F&& f, view_value_type init = {}) const {
    return std::accumulate(begin(view_), end(view_), init, std::forward<decltype(f)>(f));
  }
};

class Solution {
 public:
  int validSubarrays(vector<int>& nums) {
    return monotone_stack<int, size_view_creator<int>>(begin(nums), end(nums)).reduce(std::plus<>{});
  }
};