#include <bits/stdc++.h> using namespace std; #define ll long long #define vl vector<long long> #define pl pair<long long, long long> int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n, q; if (!(cin >> n >> q)) return 0; // 1. Načtení a spočítání četností vl input_nums(n); map<ll, ll> counts; for (ll i = 0; i < n; i++){ cin >> input_nums[i]; counts[input_nums[i]]++; } ll l_query, r_query; cin >> l_query >> r_query; // Jen načteme, v Q=1 se nepoužívá specificky jinak než přes celé pole // 2. Vytvoření párů {četnost, druh} vector<pl> pary; for (auto const& [species, count] : counts) { pary.push_back({count, species}); } // 3. Seřazení od nejméně častých po nejčastější sort(pary.begin(), pary.end()); // 4. Konstrukce optimálního rozložení (Mountain shape) // Použijeme deque pro vkládání z krajů deque<ll> final_blocks; // Procházíme seřazené páry a střídavě dáváme doleva a doprava for (int i = 0; i < pary.size(); i++) { ll count = pary[i].first; ll species = pary[i].second; // Pokud je 'i' sudé, dáme na začátek (vlevo), liché na konec (vpravo) // Tím dostaneme nejmenší na úplné kraje a největší doprostřed. if (i % 2 == 0) { // Přidáme blok zleva for(int k=0; k<count; k++) final_blocks.push_front(species); } else { // Přidáme blok zprava for(int k=0; k<count; k++) final_blocks.push_back(species); } } // Převedeme deque zpět na vector pro DP výpočet vl nums(final_blocks.begin(), final_blocks.end()); // 5. DP výpočet (tento byl správně, jen na špatně seřazeném poli) vl dp(n, 1); // Base case: dp[0] = 1 (jeden prvek má diverzitu 1) for (ll i = 1; i < n; i++){ if (nums[i] == nums[i-1]){ // Stejný druh jako předchozí -> nepřidává novou diverzitu do existujících suffixů dp[i] = dp[i-1] + 1; } else{ // Jiný druh -> pro všechny suffixy končící na i-1 se diverzita zvýší o 1 // + vznikne 1 nový suffix (samotný prvek i) // Celkem se přičte: (i) + 1 = i + 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; }