DEQ

#include <bits/stdc++.h>


struct hash_pair {
    template<class T1, class T2>
    size_t operator()(const std::pair<T1, T2> &p) const {
        auto hash1 = std::hash<T1>{}(p.first);
        auto hash2 = std::hash<T2>{}(p.second);
        if (hash1 != hash2) {
            return hash1 ^ hash2;
        }
        // If hash1 == hash2, their XOR is zero.
        return hash1;
    }

};

int T, N;
long long ans = 0;
std::multiset<int> pq;
std::deque<int> Q;
std::unordered_map<int, int> element_occurencies; // map el -> fv
std::unordered_set<std::pair<int, int>, hash_pair> edge;

int main() {
    std::cin >> N;
    std::vector<int> v(N);
    for (int i = 0; i < N; ++i)
        std::cin >> v[i];

    int i = 0;

    while (true) {

        if (element_occurencies[v[i]] > 2)
            break;

        if (Q.empty())
            Q.push_back(v[i]);
        else {
            if (pq.empty()) { // pair

                if (edge.find({Q.front(), v[i]}) == edge.end() || edge.find({v[i], Q.front()}) == edge.end()) {

                    if (Q.size() > 1) {
                        int Min = std::min(Q.front(), v[i]);
                        if (Min >= Q.back() || Q.size() == 2) {
                            ans++;
                            edge.insert({Q.front(), v[i]});
                            edge.insert({v[i], Q.front()});

                            pq.insert(Q.back());
                            Q.push_back(v[i]);
                            element_occurencies[v[i]]++;
                        }
                        else {
                            Q.pop_front();
                            Q.push_back(v[i]);
                            element_occurencies[v[i]]++;
                        }
                    } else {
                        ans++;
                        edge.insert({Q.front(), v[i]});
                        edge.insert({v[i], Q.front()});



                        Q.push_back(v[i]);
                        element_occurencies[v[i]]++;
                    }
                } else {
                    if (Q.size() > 1)
                        pq.insert(Q.back());
                    Q.push_back(v[i]);
                    element_occurencies[v[i]]++;
                }
            } else {

                int Min = std::min(Q.front(), v[i]);
                if (Min >= *pq.rbegin() && Min >= Q.back()) {
                    ans++;
                    edge.insert({Q.front(), v[i]});
                    edge.insert({v[i], Q.front()});

                    pq.insert(Q.back());
                    Q.push_back(v[i]);
                    element_occurencies[v[i]]++;
                } else {
                    while (!pq.empty() && Min < std::max(Q.back(), *pq.rbegin())) {
                        Q.pop_front();
                        pq.erase(pq.find(Q.front()));
                        Min = std::min(Q.front(), v[i]);
                    }

                    if (!pq.empty()) {
                        ans++;
                        edge.insert({Q.front(), v[i]});
                        edge.insert({v[i], Q.front()});

                        pq.insert(Q.back());
                        Q.push_back(v[i]);
                        element_occurencies[v[i]]++;
                    }
                }
            }

        }
        i = (i + 1) % N;
    }

    std::cout << ans << '\n';
    // for (const auto &e: edge)
        // std::cout << e.first << ' ' << e.second << '\n';
    return 0;
}