Tony Blair has said meeting victims of the Troubles as he wrestled with his conscience over the early release of paramilitary prisoners was the most difficult aspect of striking the Good Friday peace deal.
Reflecting on the historic accord ahead of its 20th anniversary, the former prime minister said weighing the contrasting views of the bereaved was an onerous task.
The deal that largely ended the region's 30-year sectarian conflict included a provision to facilitate the early release of around 500 paramilitary prisoners within two years.
It was a concession that almost torpedoed the accord in the final frantic hours prior to its signing on April 10 1998 - Good Friday.
Mr Blair, who cites the April 1998 agreement as one of the most important achievements of his decade in power, explained how he thought through the issue of letting killers go free.
"Some of the most difficult meetings I had as prime minister were with the families of the victims of the Troubles," he told the Press Association.
"They actually fitted into two categories of people. One group of people said 'How can you be sitting down with murderers, making and deal with them or releasing people who have committed horrendous crimes against innocent people, and my family were victim of this appalling violence?', and then there would be other people who would say 'You've got to make sure this works because I don't want other people to go through what I've been through'.
"This is where, in the end, as a political leader, you've got to decide what you think is right. These rights require choices that are difficult for the leader but they are even more difficult for the people who have been victims of the trouble."
He added: "Of course you could make the case as to why you should never release people who are engaged in acts of violence but, the fact is, if we hadn't had the prisoner release, we would never have had the peace agreement."
The deal struck between the UK and Irish governments and the main Stormont parties, with the exception of the Democratic Unionists, paved the way for a return to devolved government in Northern Ireland.
It also saw the creation of a number of cross-border political bodies, a commitment to reform policing and an undertaking from paramilitaries to decommission their weapons.
It enshrined the principle of consent - that Northern Ireland's constitutional position as part of the UK would only ever change if a majority in the region voted for it - while at the same time offering provisions that legitimised nationalist aspirations to strive for a united Ireland.
Mr Blair said he did not believe the current problems besetting powersharing, including an impasse over the Irish language, should herald the demise of the deal and insisted that powersharing remained the best way to bring deliver devolved governance to the region.
"I can't believe we can't find a way through this if we really wanted to," he said.
"My strong advice to the Prime Minister and Government is just work at this until you sort it out, because from what I am reading I can't see anything which is an absolute barrier to sorting it out."
He added: "People have just got to throw their minds back to what it was like during the Troubles.
"I do find it extraordinary sometimes when people say has life really improved - well, I think, yes, it has. I remember going to Northern Ireland, long before I became prime minister in the 1980s, and being shocked.
"Thinking I am going into a part of my country that is completely different from any other part of the country and is differently regarded by the people there and by the people outside.
"Every day you would end up with death, violence, sectarian acts of hatred and terrorism - every day. So the comparison is not between what we have now and what, ideally, we want to have - the comparison is between what we have now and what we had then, and I think if people keep their mind focused on that, they will be focused on the right thing."
Mr Blair said the three days he spent ensconced in Castle Buildings, Stormont, as he attempted to clinch the deal were some of the most extraordinary of his 10 years in power.
"It was a unique few days because we were involved in this incredibly complicated and difficult negotiation which were seesawing between success and failure throughout the three days," he said.
"What was at stake was of immense magnitude, to try to put an end to the violence in Northern Ireland that has disfigured the lives of people and cost the lives of people for many years, and it was an event which required extraordinary focus, and literally, for those three days, I think we managed six hours sleep over the whole of the time.
"We were literally camped in rooms, shuttling to and from, bringing people in, bringing them out, trying to make sure we were working on the detail of various documents at the same time as having quite high-level discussions, snatching something to eat when you could, going to the loo when you could. I'll never forgot those three days.
"I remember when I actually finished it and we announced the agreement, I had to go abroad for an engagement in Spain.
"I remember getting on the plane, and the first thing that happened was I was passed a mobile phone and the Queen was on the other line - which was literally the only time that ever happened to me - to offer her support and congratulations on the agreement. Then I remember actually, just as we were taking off, falling asleep and not waking until we landed."