#include <bits/stdc++.h> using namespace std; #define ll long long const ll mmod = 998244353; #define vl vector<long long> #define vll vector<vector<long long>> #define pl pair<long long, long long> #define vb vector<bool> int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n, q; if (!(cin >> n >> q)) return 0; vl nums(n); // Použijeme mapu pro bezpečné počítání četností (funguje i pro velká čísla druhů) map<ll, ll> counts; for (ll i = 0; i < n; i++){ cin >> nums[i]; counts[nums[i]]++; } ll l, r; cin >> l >> r; // Vytvoříme páry {četnost, druh} pouze pro unikátní druhy vector<pl> pary; for (auto const& [species, count] : counts) { pary.push_back({count, species}); } // Seřadíme podle četnosti (méně četné druhy na začátek) sort(pary.begin(), pary.end()); nums.clear(); // Rekonstrukce pole - nyní bude mít správnou délku N for (auto x : pary){ for (ll i = 0; i < x.first; i++){ nums.push_back(x.second); } } // DP výpočet celkové diverzity // dp[i] = součet diverzit všech podposloupností končících na indexu i vl dp (n, 1); // Base case pro index 0 je již nastaven na 1 for (ll i = 1; i < n; i++){ if (nums[i] == nums[i-1]){ // Pokud je zvíře stejné jako předchozí, diverzita se zvedne jen o 1 (pro samotné nové zvíře) // v rámci existujících podposloupností se "nepřičítá", protože druh už tam je. dp[i] = dp[i-1] + 1; } else{ // Pokud je to nové zvíře (vzhledem k seřazení a seskupení to znamená, // že tento druh se v předchozích podposloupnostech končících na i-1 nevyskytoval), // zvýší diverzitu všech (i+1) podposloupností končících na i o 1. dp[i] = dp[i-1] + (i + 1); } } ll suma = 0; for (ll i = 0; i < n; i++){ suma += dp[i]; } cout << suma << "\n"; return 0; }