/* input
5
63
23 34 98 12 123
*/
#include<iostream>
#include<queue>
#include<algorithm>

#define rep(i,a,b) for(int i=a;i<b;i++)
#define NC 200
#define pb push_back
#define mp make_pair

using namespace std;

double FCFS(int hp, int* req, int n){
	int time=0, pos=hp;
	rep(i,0,n){
		time += abs(req[i]-pos);
		pos = req[i];
		cout<<"\t"<<pos<<" seeked\n";
	}

	double Total_time = time ;
	return Total_time;
}

double SSTF(int hp, int* req, int n){
	int time=0, pos=hp;

	vector<int> request;
	rep(i,0,n) request.pb(req[i]);

	while(request.size()){

		int len = request.size();
		int minimum=1000,min_index;
		rep(i,0,len){
			if (minimum>abs(pos-request[i])){
				minimum = abs(pos-request[i]);
				min_index = i;
			}
		}

		pair<int,int> x = mp(minimum,min_index);

		time += x.first;
		pos = request[x.second];
		request.erase(request.begin()+x.second);

		cout<<"\t"<<pos<<" seeked\n";

	}

	double Total_time = time ;
	return Total_time;
}

double SCAN(int hp, int* req, int n){
	int time=0, pos=hp;

	vector<int> request;
	rep(i,0,n) request.pb(req[i]);

	request.pb(hp);

	int end=NC, start=0, cur=0, hp_index;

	sort(request.begin(),request.end());
	while(request[cur] != hp) cur++;

	hp_index = cur;
	cur++;
	while(cur<n+1){
		time += request[cur] - pos;
		pos = request[cur];
		cout<<"\t"<<pos<<" seeked\n";
		cur++;
	}

	// Seek to end
	time += end - pos;
	pos = end;

	cur = hp_index - 1;

	// Seek back to start
	while(cur>=0){
		time += pos - request[cur];
		pos = request[cur];
		cout<<"\t"<<pos<<" seeked\n";
		cur--;
	}

	double Total_time = time ;
	return Total_time;
}

double C_SCAN(int hp, int* req, int n){
	int time=0, pos=hp;

	vector<int> request;
	rep(i,0,n) request.pb(req[i]);

	request.pb(hp);

	int end=NC, start=0, cur=0, hp_index;

	sort(request.begin(),request.end());
	while(request[cur] != hp) cur++;

	hp_index = cur;
	cur++;
	while(cur<n+1){
		time += request[cur] - pos;
		pos = request[cur];
		cout<<"\t"<<pos<<" seeked\n";
		cur++;
	}

	// Seek to end
	time += end - pos;
	pos = end;

	// Seek back to start in no time
	pos = 0;

	cur = 0;

	while(cur<hp_index){
		time -= pos - request[cur];
		pos = request[cur];
		cout<<"\t"<<pos<<" seeked\n";
		cur++;
	}

	double Total_time = time ;
	return Total_time;
}

double C_LOOK(int hp, int* req, int n){
	int time=0, pos=hp;

	vector<int> request;
	rep(i,0,n) request.pb(req[i]);

	request.pb(hp);

	int cur=0, hp_index;

	sort(request.begin(),request.end());
	while(request[cur] != hp) cur++;

	hp_index = cur;
	cur++;
	while(cur<n+1){
		time += request[cur] - pos;
		pos = request[cur];
		cout<<"\t"<<pos<<" seeked\n";
		cur++;
	}

	// Seek to start
	// we do not add the time required for head movement from last request to first request
	pos = request[0];
	cur = 0;

	while(cur<hp_index){
		time += abs(pos - request[cur]);
		pos = request[cur];
		cout<<"\t"<<pos<<" seeked\n";
		cur++;
	}

	double Total_time = time ;
	return Total_time;
}

double LOOK(int hp, int* req, int n){
	int time=0, pos=hp;

	vector<int> request;
	rep(i,0,n) request.pb(req[i]);

	request.pb(hp);

	int cur=0, t_cur;

	sort(request.begin(),request.end());
	while(request[cur] != hp) cur++;

	t_cur = cur;
	cur++;
	while(cur<n+1){
		time += request[cur] - pos;
		pos = request[cur];
		cout<<"\t"<<pos<<" seeked\n";
		cur++;
	}

	cur = t_cur - 1;

	while(cur>=0){
		time += pos - request[cur];
		pos = request[cur];
		cout<<"\t"<<pos<<" seeked\n";
		cur--;
	}

	double Total_time = time;
	return Total_time;
}

int main(){
	int n,hp;
	cout<<"DISK SCHEDULING\n";
	cout<<"No. of requests : ";
	cin>>n;
	cout<<"Initial Position of Head (Total Cylinder : "<<NC<<" ) : ";
	cin>>hp;
	int err=0;
	cout<<"Provide Positions to Visit : max is 200\n";
	int req[n];
	rep(i,0,n) cin>>req[i];

	// Comparing the disk scheduling algorithms:
	cout<<"============================================\n";
	cout<<"--- FCFS ---\n";
	cout<<"Total seek time : \n"<<FCFS(hp, req, n)<<"\n\n";
	cout<<"============================================\n";
	cout<<"--- SSTF ---\n";
	cout<<"Total seek time : \n"<<SSTF(hp, req, n)<<"\n\n";
	cout<<"============================================\n";
	cout<<"--- SCAN ---\n";
	cout<<"Total seek time : \n"<<SCAN(hp, req, n)<<"\n\n";
	cout<<"============================================\n";
	cout<<"--- C_SCAN ---\n";
	cout<<"Total seek time : \n"<<C_SCAN(hp, req, n)<<"\n\n";
	cout<<"============================================\n";
	cout<<"--- LOOK ---\n";
	cout<<"Total seek time : \n"<<LOOK(hp, req, n)<<"\n\n";
	cout<<"============================================\n";
	cout<<"--- C_LOOK ---\n";
	cout<<"Total seek time : \n"<<C_LOOK(hp, req, n)<<"\n\n";
	cout<<"============================================\n";

	return 0;
}