#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
#define pvec(vec) {for (auto v: vec) cout << v << ' '; cout << endl;}
#define pivec(vec) {rep(i, 0, vec.size()) cout << i << ':' << vec[i] << ' '; cout << endl;}

using namespace std;
using ll = long long;

// Binary Indexed Tree (Fenwick Tree)
template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};

int main()
{
    int N, Q;
    cin >> N >> Q;

    // read input as range 
    vector<pair<int, int>> clr_rng;
    {
        unordered_map<int, int> prepos;
        rep(i, 1, N+1)
        {
            int c;
            cin >> c;
            clr_rng.emplace_back(prepos[c], i);
            prepos[c] = i;
        }
    }
    vector<tuple<int, int, int>> qry;
    rep(i, 0, Q)
    {
        int l, r;
        cin >> l >> r;
        qry.emplace_back(l, r, i);
    }


    // sort by start pos 
    sort(clr_rng.rbegin(), clr_rng.rend());
    sort(qry.rbegin(), qry.rend());

    // countint with bit
    BIT<ll> bit(N+1);
    vector<int> ans(Q);
    int pos_c = 0;
    int pos_q = 0;
    rrep(pos, N+1, 1)
    {
        // add range
        while (pos_c < (int) clr_rng.size())
        {
            int frm, to;
            tie(frm, to) = clr_rng[pos_c];
            if (frm < pos) break;

            // printf("from: %d, to: %d\n", frm, to);

            bit.add(to, 1);
            ++pos_c;
        }

        // process query
        while (pos_q < (int) qry.size())
        {
            int frm, to, i;
            tie(frm, to, i) = qry[pos_q];
            if (frm < pos) break;

            int num = to - frm + 1;
            num -= bit.sum(to);

            // printf("from: %d, to: %d, i: %d, bit: %lld\n", frm, to, i, bit.sum(to));

            ans[i] = num;
            ++pos_q;
        }

    }

    // output answer
    rep(i, 0, Q) printf("%d\n", ans[i]);

    return 0;
}


#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>
// #include<assert.h>
#include<random>
using namespace std;
#define int long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
// #define MOD 998244353 
#define MEM_SIZE 100010
#define DEBUG_OUT true
#define ALL(x) (x).begin(), (x).end()

template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

//https://www.youtube.com/watch?v=RDaGj_ztNz4&feature=youtu.be

//-----CODE------//

int dfs(int v,int c,vector<vector<int> > & GRAPH,vector<int> & color)
{

  color[v] = c;
  // DEBUG(color);
  for (auto &&u : GRAPH[v])
  {
    if(color[u] == c)
    {
      return false;
    }
    
    if(color[u] ==0 && !dfs(u,-1*c,GRAPH,color))
    {
    return false;
    }
  }
  return true;
  
}
void solve(void)
{
  int n,m;
  cin>>n>>m;
  vector<vector<int> > GRAPH (n);
  for (int i = 0; i < m; i++)
  {
    int A,B;
    cin>>A>>B;
    A--;B--;
    GRAPH[A].push_back(B);
    GRAPH[B].push_back(A);
  }
  int b = 0,w = 0;
  vector<int> color(n,0);
  if(dfs(0,1,GRAPH,color))
  {
    for (int i = 0; i < n; i++)
    {
      if(color[i] == 1)
      {
        b++;
      }
      else if(color[i] == -1)
      {
        w++;
      }
    }
    cout<<b*w - m <<endl;
    
  }
  else
  {
    cout<<n*(n-1)/2 - m<<endl;
  }
  


  

  return;
}

int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(11);
  solve();

  return 0;
}
