/// @file ss.cc
/// @brief ss の実装ファイル
/// @author Yusuke Matsunaga (松永 裕介)
///
/// Copyright (C) 2019 Yusuke Matsunaga
/// All rights reserved.


#include <iostream>
#include <vector>
#include <unordered_map>

bool debug_heap = false;

using namespace std;

struct Cell
{
  int pos;
  int val;
  int min_index;
  int max_index;
};

class Heap
{
public:

  Heap(int max_heap);

  ~Heap();


public:

  void
  put(Cell* cell);

  void
  del(Cell* cell);

  int
  min() const;

  int
  max() const;

  void
  dump(ostream& s) const;

  void
  dump_minheap(ostream& s) const;

  void
  dump_maxheap(ostream& s) const;


private:

  void
  min_move_down(Cell* cell);

  void
  min_move_up(Cell* cell);

  void
  min_locate(Cell* cell,
	     int index);

  void
  max_move_down(Cell* cell);

  void
  max_move_up(Cell* cell);

  void
  max_locate(Cell* cell,
	     int index);

  void
  sanity_check();


private:

  int mNum;

  vector<Cell*> mMinHeap;

  vector<Cell*> mMaxHeap;

};

Heap::Heap(int max_heap) :
  mNum{0},
  mMinHeap(max_heap),
  mMaxHeap(max_heap)
{
}

Heap::~Heap()
{
}

void
Heap::put(Cell* cell)
{
  if ( debug_heap) {
    cout << "before put(" << cell->val << ")" << endl;
    dump(cout);
  }

  min_locate(cell, mNum);
  max_locate(cell, mNum);
  ++ mNum;

  min_move_up(cell);
  max_move_up(cell);

  if ( debug_heap ) {
    sanity_check();
  }
}

void
Heap::del(Cell* cell)
{
  if ( debug_heap ) {
    cout << "before del(" << cell->val << ")" << endl;
    dump(cout);
  }

  auto p_mincell = mMinHeap[mNum - 1];
  if ( cell->min_index < mNum - 1) {
    min_locate(p_mincell, cell->min_index);
    min_move_down(p_mincell);
    min_move_up(p_mincell);
  }
  mMinHeap[mNum] = nullptr;

  auto p_maxcell = mMaxHeap[mNum - 1];
  if ( cell->max_index < mNum - 1) {
    max_locate(p_maxcell, cell->max_index);
    max_move_down(p_maxcell);
    max_move_up(p_maxcell);
  }
  mMaxHeap[mNum] = nullptr;

  -- mNum;

  if ( debug_heap ) {
    sanity_check();
  }
}

int
Heap::min() const
{
  const auto cell = mMinHeap[0];
  return cell->val;
}

int
Heap::max() const
{
  const auto cell = mMaxHeap[0];
  return cell->val;
}

void
Heap::min_move_down(Cell* cell)
{
  int pos = cell->min_index;
  while ( true ) {
    int l_pos = pos * 2 + 1;
    int r_pos = pos * 2 + 2;
    if ( l_pos >= mNum ) {
      // 子供を持たない場合
      break;
    }
    auto cell = mMinHeap[pos];
    auto l_cell = mMinHeap[l_pos];
    if ( r_pos >= mNum ) {
      // 左の子供のみを持つ場合
      if ( l_cell->val < cell->val ) {
	min_locate(cell, l_pos);
	min_locate(l_cell, pos);
      }
      break;
    }
    else {
      // 両方の子供を持つ場合
      auto r_cell = mMinHeap[r_pos];
      if ( l_cell->val < r_cell->val ) {
	if ( l_cell->val < cell->val ) {
	  min_locate(cell, l_pos);
	  min_locate(l_cell, pos);
	  pos = l_pos;
	}
	else {
	  break;
	}
      }
      else {
	if ( r_cell->val < cell->val ) {
	  min_locate(cell, r_pos);
	  min_locate(r_cell, pos);
	  pos = r_pos;
	}
	else {
	  break;
	}
      }
    }
  }
}

void
Heap::min_move_up(Cell* cell)
{
  int pos = cell->min_index;
  while ( pos > 0 ) {
    int p_pos = (pos - 1) / 2;
    auto cell = mMinHeap[pos];
    auto p_cell = mMinHeap[p_pos];
    if ( cell->val < p_cell->val ) {
      min_locate(cell, p_pos);
      min_locate(p_cell, pos);
      pos = p_pos;
    }
    else {
      break;
    }
  }
}

void
Heap::min_locate(Cell* cell,
		 int index)
{
  mMinHeap[index] = cell;
  cell->min_index = index;
}

void
Heap::max_move_down(Cell* cell)
{
  int pos = cell->max_index;
  while ( true ) {
    int l_pos = pos * 2 + 1;
    int r_pos = pos * 2 + 2;
    if ( l_pos >= mNum ) {
      // 子供を持たない場合
      break;
    }
    auto cell = mMaxHeap[pos];
    auto l_cell = mMaxHeap[l_pos];
    if ( r_pos >= mNum ) {
      // 左の子供のみを持つ場合
      if ( l_cell->val > cell->val ) {
	max_locate(cell, l_pos);
	max_locate(l_cell, pos);
      }
      break;
    }
    else {
      // 両方の子供を持つ場合
      auto r_cell = mMaxHeap[r_pos];
      if ( l_cell->val > r_cell->val ) {
	if ( l_cell->val > cell->val ) {
	  max_locate(cell, l_pos);
	  max_locate(l_cell, pos);
	  pos = l_pos;
	}
	else {
	  break;
	}
      }
      else {
	if ( r_cell->val > cell->val ) {
	  max_locate(cell, r_pos);
	  max_locate(r_cell, pos);
	  pos = r_pos;
	}
	else {
	  break;
	}
      }
    }
  }
}

void
Heap::max_move_up(Cell* cell)
{
  int pos = cell->max_index;
  while ( pos > 0 ) {
    int p_pos = (pos - 1) / 2;
    auto cell = mMaxHeap[pos];
    auto p_cell = mMaxHeap[p_pos];
    if ( cell->val > p_cell->val ) {
      max_locate(cell, p_pos);
      max_locate(p_cell, pos);
      pos = p_pos;
    }
    else {
      break;
    }
  }
}

void
Heap::max_locate(Cell* cell,
		 int index)
{
  mMaxHeap[index] = cell;
  cell->max_index = index;
}

void
Heap::sanity_check()
{
  bool error = false;
  for ( int pos = 1; pos < mNum; ++ pos ) {
    int p_pos = (pos - 1) / 2;
    auto cell = mMinHeap[pos];
    auto p_cell = mMinHeap[p_pos];
    if ( cell->val < p_cell->val ) {
      cout << "ERROR in mMinHeap at " << pos << endl;
      cout << "cell->val = " << cell->val
	   << ", p_cell->val = " << p_cell->val << endl;
      error = true;
    }
  }
  for ( int pos = 1; pos < mNum; ++ pos ) {
    int p_pos = (pos - 1) / 2;
    auto cell = mMaxHeap[pos];
    auto p_cell = mMaxHeap[p_pos];
    if ( cell->val > p_cell->val ) {
      cout << "ERROR in mMaxHeap at " << pos << endl;
      cout << "cell->val = " << cell->val
	   << ", p_cell->val = " << p_cell->val << endl;
      error = true;
    }
  }
  if ( error ) {
    dump(cout);
    abort();
  }
}

void
Heap::dump(ostream& s) const
{
  dump_minheap(s);
  dump_maxheap(s);
  s << endl;
}

void
Heap::dump_minheap(ostream& s) const
{
  s << "mMinHeap" << endl;
  for ( int i = 0; i < mNum; ++ i ) {
    s << " " << mMinHeap[i]->val;
  }
  s << endl;
}

void
Heap::dump_maxheap(ostream& s) const
{
  s << "mMaxHeap" << endl;
  for ( int i = 0; i < mNum; ++ i ) {
    s << " " << mMaxHeap[i]->val;
  }
  s << endl;
}

int
main(int argc,
     char** argv)
{
  bool debug = false;

  int n, k;
  cin >> n >> k;

  vector<Cell> CellList(n);
  for ( int i = 0; i < n; ++ i ) {
    int val;
    cin >> val;
    CellList[i] = Cell{i, val, -1, -1};
  }

  if ( debug ) {
    cout << n << " " << k << endl;
    for ( int i = 0; i < n; ++ i ) {
      cout << " " << CellList[i].val;
    }
    cout << endl;
  }

  Heap heap(k);

  // 最初の K 個を調べる．
  int last_gap = -1;
  for ( int i = 0; i < k - 1; ++ i ) {
    if ( CellList[i].val > CellList[i + 1].val ) {
      last_gap = i;
    }
    heap.put(&CellList[i + 1]);
  }

  // とにかく最初のパタンは登録する．
  int num = 1;

  // 原順列と等しいパタンが有った時 true にするフラグ
  bool ident = false;
  if ( last_gap == -1 ) {
    // 先頭の K 個は整列していた．
    ident = true;
  }

  for ( int i = 1; i <= n - k; ++ i ) {
    if ( debug ) {
      cout << endl;
      cout << "i = " << i << ":";
      for ( int j = 0; j < k; ++ j ) {
	cout << " " << CellList[i + j].val;
      }
      cout << endl;
    }
    // last_gap を更新する
    if ( CellList[i + k - 2].val > CellList[i + k - 1].val ) {
      last_gap = i + k - 2;
    }

    if ( last_gap < i ) {
      // 対象の区間に変化がない．
      if ( !ident ) {
	ident = true;
	++ num;
      }
    }
    else {
      bool reverse = false;
      if ( CellList[i - 1].val > heap.min() || CellList[i + k - 1].val < heap.max() ) {
	++ num;
      }
      if ( 0 ) {
	int min = CellList[i].val;
	int max = CellList[i].val;
	for ( int j = 1; j < k - 1; ++ j ) {
	  int val = CellList[i + j].val;
	  if ( min > val ) {
	    min = val;
	  }
	  if ( max < val ) {
	    max = val;
	  }
	}
	bool error = false;
	if ( min != heap.min() ) {
	  cout << "ERROR: min = " << min << ", heap.min() = " << heap.min() << endl;
	  error = true;
	}
	if ( max != heap.max() ) {
	  cout << "ERROR: max = " << max << ", heap.max() = " << heap.max() << endl;
	  error = true;
	}
	if ( error ) {
	  for ( int j = 0; j < k - 1; ++ j ) {
	    cout << " " << CellList[i + j].val;
	  }
	  cout << endl;
	  heap.dump(cout);
	}
      }
    }
    heap.del(&CellList[i]);
    heap.put(&CellList[i + k - 1]);
  }

  cout << num << endl;
}


Measured memory_bytes: 6528